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<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
pair<int,int>f[510];
int n,mod,dp[510][260],r[510],ans;
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:0;}
bool cmp(pair<int,int>x,pair<int,int>y)
{
	return x.first==y.first?x.second>y.second:x.first<y.first;
}
int main()
{
	scanf("%d %d",&n,&mod);
	for(int i=0;i<2*n;++i)r[i]=min((int)floor(sqrt(4*n*n-i*i)),2*n-1);
	for(int i=0;i<n;++i)f[i+1]={(int)ceil(sqrt(n*n-i*i))-1,i};
	for(int i=n;i<2*n;++i)f[i+1]={r[i],i};
	sort(f+1,f+2*n+1,cmp);
//	for(int i=1;i<=2*n;++i)printf("%d ",f[i].second);printf("\n");
	for(int k=0;k<=n;++k)
	{
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		int cnt=0;
		for(int i=1;i<=2*n;++i)
			if(f[i].second>=n)
			{
				for(int j=0;j<=k;++j)dp[i][j]=1ll*dp[i-1][j]*(f[i].first+1-(i-1-(cnt-j)))%mod;
			}
			else
			{
				for(int j=0;j<=k;++j)dp[i][j]=(dp[i][j]+1ll*dp[i-1][j]*(r[f[i].second]+1-(2*n-1-f[i].second+k-j)))%mod;
				for(int j=0;j<k;++j)dp[i][j+1]=(dp[i][j+1]+1ll*dp[i-1][j]*(f[i].first+1-(i-1-(cnt-j))))%mod;
				++cnt;
			}
		if(k&1)add(ans,mod-dp[2*n][k]);
		else add(ans,dp[2*n][k]);
	}
	printf("%d",ans);
	return 0;
}
