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 <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define PII pair<int,int>
#define MP make_pair
#define fir first
#define sec second
#define PB push_back
#define db long double
#define ll long long
using namespace std;
template <class T>
inline void rd(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-'0'+c,c=getchar(); x*=f;
}
const int N=510;
int mod;
inline void Add(int &x,int y) { x=(x%mod+mod)%mod,y=(y%mod+mod)%mod; x=(x+y)%mod; } //x+=y; if(x>=mod) x-=mod; }
inline void Dec(int &x,int y) { x=(x%mod+mod)%mod,y=(y%mod+mod)%mod; x=(x-y+mod)%mod; } //x-=y; if(x<0) x+=mod; }
int n;
int f[N],g[N];
int bel[N],id[N];
int getr(int x) { return bel[x]?f[x]:g[x]; }
bool cmp(int x,int y) {
	int h1=getr(x),h2=getr(y);
	if(h1==h2) return x>y; // ?!
	return h1<h2; 
}
int ans;
int dp[N][N];
void solve(int k) {
	memset(dp,0,sizeof(dp));
	dp[0][0]=getr(id[0])+1;
	if(bel[id[0]]&&k&&g[id[0]]+1-(2*n-k)>0) dp[0][1]=g[id[0]]+1-(2*n-k);
	for(int i=1;i<2*n;++i)
		for(int j=0;j<=i&&j<=k;++j) if(dp[i-1][j]) {
			if(getr(id[i])+1-(i-j)>0) Add(dp[i][j],dp[i-1][j]*(ll)(getr(id[i])+1-(i-j))%mod);
			if(bel[id[i]]&&j<k&&g[id[i]]+1-(2*n-k+j)>0) Add(dp[i][j+1],dp[i-1][j]*(ll)(g[id[i]]+1-(2*n-k+j))%mod);
		}
//	cout<<k<<":"<<endl;
//	for(int i=0;i<2*n;++i,puts(""))
//		for(int j=0;j<=k;++j) printf("%d ",dp[i][j]); 
//	cout<<k<<' '<<dp[2*n-1][k]<<endl;
	if((n-k)&1) Dec(ans,dp[2*n-1][k]);
	else Add(ans,dp[2*n-1][k]);
}
int main() {
	rd(n),rd(mod);
	for(int i=0;i<2*n;++i) {
		f[i]=i<n?(ceil(sqrt(n*n-i*i))-1):-1;
		g[i]=min(2*n-1,(int)floor(sqrt(4*n*n-i*i)));
		bel[i]=f[i]>=0;
		id[i]=i;
//		cout<<i<<':'<<' '<<f[i]<<' '<<g[i]<<endl;
	}
	sort(id,id+n*2,cmp);
//	for(int i=0;i<2*n;++i) printf("%d : %d %d %d\n",id[i],bel[id[i]],f[id[i]],g[id[i]]);
//	for(int i=0;i<2*n;++i) printf("%d ",id[i]); puts("");
	for(int i=0;i<=n;++i) solve(i);
	printf("%d",ans);
	return 0;
}