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 maxn 505
#define fi first
#define se second
using namespace std;
int n,mod,f[maxn][maxn];
pair<int,int>a[maxn];
int solve(int k){
	int cnt1=0,cnt2=0;
	f[0][0]=1;
	for(int i=0;i<2*n;i++)
		if(a[i].se==0){//front rb in [N,2N-1] + front choose.
			for(int j=0;j<=cnt2;j++)
				f[i+1][j]=1ll*f[i][j]*(a[i].fi-(cnt1+j)+1)%mod;
			cnt1++;
		}
		else{
			//lb-1, front rb in [N,2N-1] + front choose.
			for(int j=0;j<=cnt2;j++)
				f[i+1][j+1]=1ll*f[i][j]*(a[i].fi-(cnt1+j)+1)%mod;
			//rb, all rb in [N,2N-1] + front not choose(lb_i<lb_j -> rb_i<rb_j) + k
			f[i+1][0]=0;
			for(int j=0;j<=cnt2;j++)
				f[i+1][j]=(f[i+1][j]+1ll*f[i][j]*(a[i].se-(n+cnt2-j+k)+1))%mod;
			cnt2++;
		}
	return f[2*n][k];
}
int main()
{
	scanf("%d%d",&n,&mod);
	for(int i=0;i<n;i++)
		a[i].fi=ceil(sqrt(n*n-i*i))-1,a[i].se=sqrt(4*n*n-i*i);
	for(int i=n;i<2*n;i++)
		a[i].fi=sqrt(4*n*n-i*i),a[i].se=0;
	a[0].se=2*n-1,sort(a,a+2*n);
	int ans=0;
	for(int i=n;i>=0;i--) ans=(solve(i)-ans+mod)%mod;
	printf("%d\n",ans);
}