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;
#define N 600

LL n,mod,ans,l[N],r[N],f[N];

LL sqr(LL x){return x*x;}

void upd(LL &x,LL y){x=(x+y)%mod;}

int main(){
	scanf("%lld%lld",&n,&mod);
	for (LL i=0;i<n*2;++i){
		for (LL j=0;j<n*2;++j)
			if (sqr(i)+sqr(j)<=sqr(n*2)) r[i]=j;
			else break;
		++r[i];
	}
	for (LL i=0;i<n;++i){
		for (LL j=0;j<n*2;++j)
			if (sqr(i)+sqr(j)<sqr(n)) l[i]=j;
			else break;
		++l[i];
	}
	for (LL i=0;i<=n;++i){
		memset(f,0,sizeof f); f[0]=1;
		for (LL j=n*2-1,k=n-1;j>=n||k>=0;){
			if (j<n||(k>=0&&l[k]<=r[j])){
				for (LL t=i;~t;--t){
					upd(f[t+1],f[t]*(l[k]-t-(n*2-1-j)));
					f[t]=f[t]*(r[k]-n-(n-1-k)-(i-t))%mod;
				}
				--k;
			}
			else{
				for (LL t=i;~t;--t){
					f[t]=f[t]*(r[j]-(n*2-1-j)-t)%mod;
				}
				--j;
			}
		}
		upd(ans,f[i]*(i&1?-1:1));
	}
	printf("%lld\n",(ans+mod)%mod);
	
	return 0;
}
			