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 fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 505;
int mo,n,l[N],r[N],s[N],qz[N],sz,dp[N][N];
bool cmp(int x, int y){
	int tx=l[x]==0?r[x]:l[x]-1;
	int ty=l[y]==0?r[y]:l[y]-1;
	if(tx!=ty)return tx<ty;
	return x>y;
}
int main() {
	read(n);read(mo);
	rep(i,0,n*2-1){
		rep(j,0,2*n-1)if(i*i+j*j>=n*n&&i*i+j*j<=4*n*n)r[i]=j;
		per(j,2*n-1,0)if(i*i+j*j>=n*n&&i*i+j*j<=4*n*n)l[i]=j;
	//	printf("%d:%d %d\n",i,l[i],r[i]);
	}
	rep(i,0,2*n-1)s[++sz]=i;
	sort(s+1,s+sz+1,cmp);
	int tot=0,res=0;rep(i,0,2*n-1)tot+=l[i]>0;
	rep(i,1,sz)qz[i]=(i-1>=0?qz[i-1]:0)+(l[s[i]]==0);
//	rep(i,1,sz)
	rep(t,0,tot){
		memset(dp,0,sizeof(dp));dp[0][0]=1;
		rep(i,0,sz-1)rep(j,0,min(i,t))if(dp[i][j]){
			if(l[s[i+1]]==0)dp[i+1][j]=(dp[i+1][j]+1LL*dp[i][j]*(r[s[i+1]]+1-qz[i]-j))%mo;
			else{
				dp[i+1][j+1]=(dp[i+1][j+1]+1LL*dp[i][j]*(l[s[i+1]]-qz[i]-j))%mo;
				dp[i+1][j]=(dp[i+1][j]+1LL*dp[i][j]*(r[s[i+1]]+1-(2*n-1-(s[i+1]-(t-j)))))%mo;
			}
		}
		res=(res+1LL*(t&1?-1:1)*dp[sz][t])%mo;
	//	cerr<<t<<' '<<dp[sz][t]<<endl;
	}
	printf("%d\n",(res+mo)%mo);
	return 0;
}
