Given is an integer N. How many permutations (P_0,P_1,\cdots,P_{2N-1}) of (0,1,\cdots,2N-1) satisfy the following condition?

* For each i (0 \leq i \leq 2N-1), N^2 \leq i^2+P_i^2 \leq (2N)^2 holds.



Since the number can be enormous, compute it modulo M.

Constraints

* 1 \leq N \leq 250
* 2 \leq M \leq 10^9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M


Output

Print the number of permutations that satisfy the condition, modulo M.

Examples

Input

2 998244353


Output

4


Input

10 998244353


Output

53999264


Input

200 998244353


Output

112633322
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int n,P;
int l[N],r[N];
pair<int,int>a[N];
long long dp[N][N];
long long calc(int k)
{
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	int c1=0,c2=0;
	for(int i=0;i<n+n;i++)
		if(a[i].second==0)
		{
			for(int j=0;j<=c2;j++)
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].first+1-(c1+j))%P)%P;
			c1++;
		}
		else
		{
			for(int j=0;j<=c2;j++)
				dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(a[i].first+1-(c1+j))%P)%P;
			for(int j=0;j<=c2;j++)
				dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].second+1-(n+k+(c2-j)))%P)%P;
			c2++;
		}
	return dp[n+n][k];
}
int main()
{
	scanf("%d%d",&n,&P);
	for(int i=0;i<n;i++)
		l[i]=max((int)ceil(sqrt(n*n-i*i)),0),r[i]=min((int)floor(sqrt(4*n*n-i*i)),n+n-1),a[i]=make_pair(l[i]-1,r[i]);
	for(int i=n;i<n+n;i++)
		l[i]=0,r[i]=sqrt(4*n*n-i*i),a[i]=make_pair(r[i],0);
	sort(a,a+n+n);
	long long ans=0;
	for(int i=n;i>=0;i--)
		if(i&1) ans=(ans-calc(i)+P)%P;
		else ans=(ans+calc(i))%P;
	printf("%lld",ans);
	return 0;
}