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>
using namespace std;
#define int long long
const int N=1005;
int dp[N][N],n,M,tot,ans;
struct Ask{
	int x,y,z,to;
}A[N];
int cmp(Ask x,Ask y){
	return x.x<y.x||(x.x==y.x&&x.to<y.to);
}
signed main(){
	scanf("%lld%lld",&n,&M);
	for (int i=0;i<n;i++){
		A[++tot].x=(int)sqrt(n*n-i*i-1)+1;
		A[tot].y=1;
		A[tot].to=i==0?2*n:(int)sqrt(4*n*n-i*i)+1;
		A[++tot].x=(int)sqrt(4*n*n-(i+n)*(i+n))+1;
		A[tot].y=2;
	}
	sort(A+1,A+tot+1,cmp);
	for (int i=1;i<=tot;i++){
		A[i].z=A[i-1].z;
		if (A[i].y==2)A[i].z++;
		else A[i].to-=i-1-A[i].z;
	}
	for (int k=0;k<=n;k++){
		memset(dp,0,sizeof dp);
		dp[0][0]=1;
		for (int i=1;i<=tot;i++)
			for (int j=0;j<=i;j++){
				if (A[i].y==1){
					if (j)(dp[i][j]+=(M-1)*dp[i-1][j-1]%M*(A[i].x-j+1-A[i].z))%=M;
					(dp[i][j]+=dp[i-1][j]*(A[i].to-(k-j)-A[tot].z))%=M;
				}
				if (A[i].y==2)
					if ((A[i].x-A[i].z+1-j)>0)(dp[i][j]+=dp[i-1][j]*(A[i].x-A[i].z+1-j))%=M;
			}
		(ans+=dp[tot][k])%=M;	
	}
	printf("%lld\n",ans);
}