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 fo(i,a,b)for(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
#define ll long long
using namespace std;
const int N=505;
int n,mo,ans,f[N][N],s;
struct nod{
	int i,l,r;
}a[N];
bool cmp(nod x,nod y){
	if(x.i<n){
		if(y.i<n)return x.l<y.l||x.l==y.l&&x.r<y.r;
		return x.l<=y.r;
	}
	if(y.i<n)return x.r<y.l;
	return x.r<y.r;
}
int sqrt1(int n){
	int a=sqrt(n);
	for(;a*a<=n;)++a;
	for(;a*a>n;)--a;
	return a;
}
int sqrt2(int n){
	int a=sqrt(n);
	for(;a*a<n;)++a;
	for(;a*a>=n;)--a;
	return a;
}
int main(){
	cin>>n>>mo;
	fo(i,0,n-1)a[i]=(nod){i,sqrt2(n*n-i*i),sqrt1(n*n*4-i*i)};
	fo(i,n,n*2-1)a[i]=(nod){i,0,sqrt1(n*n*4-i*i)};
	a[0].r=n*2-1;
	sort(a,a+n*2,cmp);
	fo(k,0,n){
		memset(f,0,sizeof f);
		f[0][0]=1;
		s=0;
		fo(i,0,n*2-1)
			if(a[i].i>=n){
				fo(j,0,min(s,k))
					if(a[i].r+1>=(i-s+j))
						f[i+1][j]=(ll)f[i][j]*(a[i].r+1-(i-s+j))%mo;
			}else{
				fo(j,0,min(s,k)){
					if(a[i].l+1>=(i-s+j))
						f[i+1][j+1]=(ll)f[i][j]*(a[i].l+1-(i-s+j))%mo;
					if(a[i].r+1>=(n+s+k-j))
						f[i+1][j]=((ll)f[i][j]*(a[i].r+1-(n+s+k-j))+f[i+1][j])%mo;
				}
				++s;
			}
		ans=(ans+f[n*2][k]*(k&1?-1:1))%mo;
	}
	cout<<(ans+mo)%mo;
}