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;
const int maxn=600;
int n,m,cnt1,cnt2;
long long Ans=0,f[maxn][maxn];
struct point{
	int f,s;
}p[maxn];
inline long long read(){
	long long x=0,f=1;
	char c;
	do{c=getchar();if(c=='-') f*=-1;}while(!isdigit(c));
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
bool cmp(const point a,const point b){return (a.f==b.f)?(a.s<b.s):(a.f<b.f);}

int main(){
	n=read();m=read();
	for(int i=0;i<n;i++){
		p[i].f=sqrt((n*n-1)-i*i);
		p[i].s=min(2*n-1,(int)sqrt((4*n*n)-i*i));
	}
	for(int i=n;i<2*n;i++){
		p[i].f=sqrt((4*n*n)-i*i);
		p[i].s=0;
	}
	sort(p,p+2*n,cmp);
	for(int k=0;k<=n;k++){
		memset(f,0,sizeof(f));
		cnt1=cnt2=0;
		f[0][0]=1;
		for(int i=1;i<=2*n;i++){
			if(p[i-1].s==0){
				for(int j=0;j<=cnt1;j++){
					(f[i][j]+=f[i-1][j]*(p[i-1].f+1-cnt2-j))%=m;
				}
				cnt2++;
			}
			else{
				for(int j=0;j<=cnt1;j++){
					(f[i][j+1]+=f[i-1][j]*(p[i-1].f+1-cnt2-j))%=m;
					(f[i][j]+=f[i-1][j]*(p[i-1].s+1-n-k-(cnt1-j)))%=m;
				}
				cnt1++;
			}
		}
		Ans=(Ans+m+(k%2==0?1:-1)*f[2*n][k])%m;
	}
	printf("%lld\n",Ans);
	return 0;
}