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;

typedef long long LL;

const int N=500;

int mod;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

int n;

void into(){
  scanf("%d%d",&n,&mod);
}

int l[N+9],r[N+9];
struct position{
  int p,id;
}a[N+9];

bool cmp(const position &a,const position &b){return a.p<b.p||a.p==b.p&&a.id>b.id;}

void Get_a(){
  for (int i=0;i<n<<1;++i){
	r[i]=min((int)floor(sqrt(4*n*n-i*i)),2*n-1);
	l[i]=max((int)ceil(sqrt(n*n-i*i)),0);
	a[i].id=i;
	a[i].p=i<n?l[i]-1:r[i];
  }
  sort(a,a+n*2,cmp);
}

int dp[N+9][N+9],ans;

void Get_dp(int c){
  int cnt=0;
  for (int i=0;i<=n<<1;++i)
	for (int j=0;j<=n<<1;++j) dp[i][j]=0;
  dp[0][0]=1;
  for (int i=1;i<=n<<1;++i){
	position t=a[i-1];
	if (t.id<n) ++cnt;
	for (int j=0;j<=c&&j<=cnt;++j)
	  if (t.id<n){
		dp[i][j]=mul(dp[i-1][j],r[t.id]+1-(n*2-1-t.id+c-j));
		if (j>0) sadd(dp[i][j],mul(dp[i-1][j-1],t.p+1-(i-1-cnt+j)));
	  }else dp[i][j]=mul(dp[i-1][j],t.p+1-(i-1-cnt+j));
  }
  c&1?ssub(ans,dp[n<<1][c]):sadd(ans,dp[n<<1][c]);
}

void Get_dp(){
  for (int i=0;i<=n;++i) Get_dp(i);
}

void work(){
  Get_a();
  Get_dp();
}

void outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}