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;
int f[505][505],up[505],dw[505];
pair<int,int> v[505];

int main(){
	int n,M;
	scanf("%d%d",&n,&M);
	for(int i=0;i<2*n;i++){
		up[i]=sqrt(2*n*2*n-i*i);
		if(up[i]==2*n)up[i]--;
		if(i<n){
			dw[i]=sqrt(n*n-i*i-1);
			v[i]=make_pair(dw[i],n-1-i);
		}else v[i]=make_pair(up[i],i);
	}
	sort(v,v+2*n);
	for(int i=0;i<2*n;i++)if(v[i].second<n)v[i].second=n-1-v[i].second;
	int ans=0;
	for(int i=0;i<=n;i++){
		memset(f,0,sizeof(f));
		if(v[0].second<n){
			f[0][0]=v[0].first+1;
			f[0][1]=max(up[v[0].second]-n-(n-i)+1,0);
		}else{
			f[0][0]=v[0].first+1;
		}
		for(int j=1;j<2*n;j++)
			for(int k=0;k<=min(i,j+1);k++)
				if(v[j].second<n)f[j][k]=((k>0?1ll*f[j-1][k-1]*max(up[v[j].second]-n-(n-i)-(k-1)+1,0):0)+1ll*f[j-1][k]*max(v[j].first-(j-k)+1,0))%M;
				else f[j][k]=1ll*f[j-1][k]*max(v[j].first-(j-k)+1,0)%M;
		if((n-i)&1)ans=(ans-f[2*n-1][i]+M)%M;
		else ans=(ans+f[2*n-1][i])%M;
	}
	printf("%d\n",ans);
}