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<bits/stdc++.h>
#define N 550
#define LL long long
using namespace std;
int n,nn,m;
int l[N],r[N];
pair<int,int>p[N];
int dp[N][N];
inline int getf(int k,const int mod=m){
	dp[0][0]=1;
	for(int i=1,t=0;i<=nn;++i){
		int id=-p[i].second;
		for(int j=0;j<=i&&j<=k;++j){
			dp[i][j]=0;
			if(id>=n){
				dp[i][j]=1ll*dp[i-1][j]*(r[id]+1-(i-1)+(t-j))%mod;
			}
			else{
				int val=1ll*dp[i-1][j]*(r[id]+1-(nn-id-1+k-j))%mod;
				if(val>=0)dp[i][j]=val;
				if(j) dp[i][j]=(1ll*dp[i-1][j-1]*(l[id]-(j-1+i-1-t))+dp[i][j])%mod;
			}
//			printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
		}
		t+=id<n;
	}
	return dp[nn][k];
}
int main(){
	cin>>n>>m;nn=n<<1;
	const int mod=m;
	for(int i=0;i<nn;++i){
		l[i]=nn;r[i]=0;
		for(int j=0;j<nn;++j)
			if(i*i+j*j>=n*n&&i*i+j*j<=4*n*n)
				l[i]=min(l[i],j),r[i]=max(r[i],j);
//		printf("l:%d r:%d\n",l[i],r[i]);
	}
	for(int i=0;i<n;++i)p[i+1]=make_pair(l[i]-1,-i);
	for(int i=n;i<nn;++i)p[i+1]=make_pair(r[i],-i);
	sort(p+1,p+nn+1);
//	for(int i=1;i<=nn;++i)printf("%d\n",p[i].second);
	int ans=0;
	for(int i=0;i<=n;++i){
//		cout<<i<<" "<<getf(i)<<endl;
		if(i&1)ans+=mod-getf(i);
		else ans+=getf(i);
		if(ans>=mod)ans-=mod;
	}
	cout<<ans<<endl;
	return 0;
}