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=508,inf=0x3f3f3f3f;
int read(){
    int f=1,g=0;char ch=getchar();
    for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
    for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
    return f*g;
}
int ans,n,p,f[N][N];
pair<int,int> a[N];
void check(int &x,int y){if((x+=y)>=p) x-=p;}
int solve(int K){
	int cnt1=0,cnt2=0;
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for (int i=0;i<2*n;i++)
	if (!a[i].second){
		for (int j=0;j<=cnt2;j++)
		f[i+1][j]=(ll)f[i][j]*(a[i].first-(j+cnt1)+1)%p;
		cnt1++;
	}
	else{
		for (int j=0;j<=cnt2;j++)
		f[i+1][j+1]=(ll)f[i][j]*(a[i].first-(cnt1+j)+1)%p;
		for (int j=0;j<=cnt2;j++)
		check(f[i+1][j],(ll)f[i][j]*(a[i].second-(n+cnt2-j+K)+1)%p);
		cnt2++;
	}
	return (K&1) ? (p-f[2*n][K]) : f[2*n][K];
}
int main(){
	n=read();p=read();
	for (int i=0;i<n*2;i++)
	if (i<n) a[i]=make_pair((int)sqrt(n*n-1-i*i),min(n*2-1,(int)sqrt(n*n*4-i*i)));
	else a[i]=make_pair(min(n*2-1,(int)sqrt(n*n*4-i*i)),0);
	sort(a,a+n*2);
	for (int i=0;i<=n;i++) check(ans,solve(i));
	printf("%d\n",ans);
	return 0;
}
