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 ll long long
using namespace std;
const int N=505;
int n,mod,cnt;
pair<int,int> s[N];
int dp[N][N];
int main(){
	scanf("%d%d",&n,&mod);
	int lim1=n*n,lim2=n*n*4;
	for(int i=0;i<n*2;++i){
		int f=-1,g=-1;
		for(int j=n*2-1;~j;--j) if(i*i+j*j<=lim2){ f=j; break; }
		for(int j=n*2-1;~j;--j) if(i*i+j*j< lim1){ g=j; break; }
		if(g==-1) s[++cnt]=make_pair(f,0);
		else s[++cnt]=make_pair(g,f);
	}
	sort(s+1,s+cnt+1); int ans=0;
	for(int k=0;k<=n;++k){
		memset(dp,0,sizeof(dp)); dp[0][0]=1; int c1=0,c2=0;
		for(int i=1;i<=cnt;++i){
			if(!s[i].second){
				int f=s[i].first;
				for(int j=0;j<=n;++j) if(dp[i-1][j]) (dp[i][j]+=1ll*dp[i-1][j]*max(f+1-c1-j,0)%mod)%=mod;
				++c1;
			}
			else{
				int g=s[i].first,f=s[i].second;
				for(int j=0;j<=n;++j) if(dp[i-1][j]){
					(dp[i][j+1]+=1ll*dp[i-1][j]*max(g+1-c1-j,0)%mod)%=mod;
					(dp[i][j]+=1ll*dp[i-1][j]*max(f+1-k-n-c2+j,0)%mod)%=mod;
				} ++c2;
			}
		}
		if(k&1) (ans+=mod-dp[cnt][k])%=mod;
		else (ans+=dp[cnt][k])%=mod;
	}
	return printf("%d\n",ans),0;
}
 