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 ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=505;
int n,P,Ans,f[N][N],q[N];
struct Node{int l,r;}p[N];
bool cmp(int x,int y){
	if(p[x].l==p[y].l)return x>y;
	return p[x].l<p[y].l;
}
int Mod(int x){return x>=P?x-P:x;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),P=read();
	for(int i=0,l=0,r=0;i<2*n;i++){
		for(l=0;i*i+l*l<n*n;l++);
		for(r=l;i*i+(r+1)*(r+1)<=4*n*n&&r+1<2*n;r++);
		if(i<n)p[i]=(Node){l-1,r};
		else p[i]=(Node){r,l};q[i+1]=i;
	}sort(q+1,q+2*n+1,cmp);
	for(int k=0;k<=n;k++){
		f[0][0]=1;
		for(int i=1,t=0;i<=2*n;i++){
			int l=p[q[i]].l,r=p[q[i]].r;
			if(l>r)swap(l,r);
			for(int j=0;j<=min(i,k);j++){
				if(q[i]>=n)f[i][j]=1ll*f[i-1][j]*max(0,r+1-(i-1-(t-j)))%P;
				else{
					int t1=1ll*f[i-1][j]*max(0,r+1-(2*n-1-q[i]+(k-j)))%P;
					int t2=1ll*(j>=1?f[i-1][j-1]:0)*max(0,l+1-(i-1-(t-(j-1))))%P;
					f[i][j]=Mod(t1+t2);
				}
			}t+=(q[i]<n);
		}
		Ans=Mod(Ans+1ll*(k&1?P-1:1)*f[2*n][k]%P);
	}printf("%d",Ans);
	return 0;
}