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;
int n,m,mod,l[525],r[525];
ll f[525][252],ans;
pair<int,int> a[525]; 
inline ll calc(int k){
	memset(f,0,sizeof(f));
	int c1=0,c2=0; f[0][0]=1;
	for(int i=1;i<=m;c1+=(a[i].second==0),c2+=(a[i].second!=0),++i) for(int j=0;j<=i&&j<=k;++j){
		if(a[i].second==0) (f[i][j]+=f[i-1][j]*(a[i].first-c1-j))%=mod; 
		else{
			if(j) (f[i][j]+=f[i-1][j-1]*(a[i].first-j-c1+1))%=mod;
			(f[i][j]+=f[i-1][j]*(a[i].second-k-n-(c2-j)))%=mod;
		}
	}
	return f[m][k];
}
int main(){
	cin>>n>>mod; m=n<<1;
	for(int i=0;i<m;++i){
		l[i]=0; r[i]=m-1;
		while(l[i]<m&&l[i]*l[i]+i*i<n*n) ++l[i];
		while(r[i]>0&&r[i]*r[i]+i*i>m*m) --r[i];
		--l[i];
		if(i<n) a[i+1]=make_pair(l[i]+1,r[i]+1);
		else a[i+1]=make_pair(r[i]+1,0);
	}
	sort(a+1,a+m+1);
	for(int i=0;i<=n;++i) (ans+=((i&1)?-1:1)*calc(i))%=mod;
	cout<<(ans%mod+mod)%mod<<endl;
	return 0;
}