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<cstdlib>
#include<algorithm>
int N,M;
struct range{
	int i,l,r,x;
	bool operator<(const range&b)const{return x<b.x||x==b.x&&i>b.i;}
}a[510];
int f[510];
int min(int a,int b){return a<b?a:b;}
int main(){
	scanf("%d%d",&N,&M);
	int cnt=0,ans=0;
	for(int i=N*2;i--;){
		a[i]=a[i+1];
		a[i].i=i;
		while(a[i].l*a[i].l+i*i<N*N)a[i].l++;
		while(a[i].r<N*2&&a[i].r*a[i].r+i*i<=N*N*4)a[i].r++;
		a[i].x=!a[i].l?++cnt,a[i].r:a[i].l;
	}
	std::sort(a,a+N*2);
	for(int k=0;k<=N*2-cnt;k++){
		for(int i=0;i<=k;i++)f[i]=!i;
		for(int i=0,c=0;i<N*2;i++){
			int l=-min(N*2-cnt-i+c-k,0),r=min(i-c,k);
			if(a[i].l){
				for(int j=r;j>=l;j--){
					f[j+1]=(f[j+1]-1ll*f[j]*(a[i].l-c-j))%M;
					f[j]=1ll*f[j]*(a[i].r-cnt-k-(i-c-j))%M;
				}
			}
			else{
				for(int j=r;j>=l;j--)f[j]=1ll*f[j]*(a[i].r-c-j)%M;
				c++;
			}
		}
		ans=(ans+f[k])%M;
	}
	printf("%d\n",(ans+M)%M);
}