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<cstdio>
#include<algorithm>
using namespace std;
const int N=505;
int n,mod,f[N][N],ans;
pair<int,int>a[N];
#define sqr(x) (x)*(x)
int main(){
	scanf("%d%d",&n,&mod);
	for(int i=0;i<n;++i){
		while(sqr(i)+sqr(a[i].first)<sqr(n))++a[i].first;
		--a[i].first;a[i].second=n+n-1;
		while(sqr(i)+sqr(a[i].second)>sqr(n+n))--a[i].second;
	}
	for(int i=n;i<n+n;++i){
		a[i].first=n+n-1;
		while(sqr(i)+sqr(a[i].first)>sqr(n+n))--a[i].first;
	}
	sort(a,a+n+n);
	for(int t=0;t<=n;++t){
		f[0][0]=1;
		for(int i=0,s1=0,s2=0;i<n+n;++i)
			if(!a[i].second){
				for(int j=0;j<=t;++j)
					f[i+1][j]=1ll*f[i][j]*(a[i].first+1-(s1+j))%mod;
				++s1;
			}else{
				for(int j=0;j<=t;++j)
					f[i+1][j]=1ll*f[i][j]*(a[i].second+1-(n+s2+t-j))%mod;
				for(int j=0;j<t;++j)
					f[i+1][j+1]=(f[i+1][j+1]+1ll*f[i][j]*(a[i].first+1-(s1+j)))%mod;
				++s2;
			}
		ans=(ans+(t&1?mod-f[n+n][t]:f[n+n][t]))%mod;
	}
	printf("%d\n",ans);
	return 0;
}
