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 For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define fi first
#define se second
#define PB push_back
#define ll long long
using namespace std;
const int N=505;
int n,mo,l[N],r[N];
int S[N],f[N][N][N];
int main(){
	scanf("%d%d",&n,&mo);
	For(i,0,2*n-1){
		for (;i*i+l[i]*l[i]<n*n;l[i]++); l[i]++;
		for (;i*i+r[i]*r[i]<=4*n*n&&r[i]!=2*n;r[i]++);
	}
	For(i,0,n) For(j,n+1,2*n-1)
		S[i]+=((l[i]-1)>=r[j]);
	For(i,0,n+1) f[n+1][0][i]=1;
	Rep(i,n,0) For(j,0,n-i) For(k,0,i+1){
		int now=S[i+1]+j,val=1;
		Rep(p,2*n-1-S[i+1],2*n-S[i]) if (l[i+1]-1<r[p]&&r[p]<=l[i]-1) val=1ll*val*max(r[p]-now,0)%mo,++now;
		f[i][j+1][k]=(f[i][j+1][k]+mo-1ll*max(l[i]-now-1,0)*val%mo*f[i+1][j][k]%mo)%mo;
		if (k) f[i][j][k-1]=(f[i][j][k-1]+1ll*max(r[i]-(2*n-k),0)*val%mo*f[i+1][j][k])%mo;
	}
	int ans=0;
	For(i,0,n+1){
		int now=S[0]+i,val=f[0][i][0];
		Rep(p,2*n-1,n+1) if (l[0]-1<r[p]) val=1ll*val*max(r[p]-now,0)%mo,++now;
		ans=(ans+val)%mo;
	}
	printf("%d\n",ans);
}