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>
using namespace std;
#define int long long
int mod;
void add(int &x,int y){
	x=(x+y+mod)%mod;
}
int mul(int x,int y){
	return x*y%mod;
}
int sadd(int x,int y){
	return (x+y)%mod;
}
pair<int,int> a[505];
int f[505][505];
signed main(){
	int n,l,r,cnt=0;
	cin>>n>>mod;
	l=2*n-1; r=2*n-1;
	for(int i=0;i<=2*n-1;++i){
		while(i*i + l*l >= n*n && l>=0) --l;
		while(i*i + r*r > 4*n*n && r>=0) --r;
		if(l==-1) a[++cnt]=make_pair(r+1,0);
		else a[++cnt]=make_pair(l+1,r+1);
	}
	sort(a+1,a+cnt+1);
	int ans=0;
	for(int k=0;k<=n;++k){
		memset(f,0,sizeof(f));f[0][0]=1;
		for(int i=1,F=0,g=0;i<=cnt;F+=(a[i].second!=0),g+=(a[i].second==0),++i)
			for(int j=0;j<=k;++j){
				int now=f[i-1][j];
				if(a[i].second==0) add(f[i][j],mul(now,a[i].first-g-j));
				//g表示前面参与前缀计数的,j表示容斥时参与前缀计数的
				else{
					if(j!=k) add(f[i][j+1],mul(now,a[i].first-g-j));
					add(f[i][j],mul(now,a[i].second-(F-j)-k-n));
				} 
			}
		if(k&1) add(ans,mod-f[cnt][k]);
		else add(ans,f[cnt][k]);
	}
	cout<<ans; 
	return 0;
} 