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<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (lc|1)
using namespace std;
inline int read(){
	int x=0; bool f=0; char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f=(ch=='-');
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}

int n,mod,ans;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

bool v[505][505];
int l[505],r[505],id;
struct node{int x,y,id;}nd[505];
inline bool jud(node a,node b){
	if(a.x==b.x&&a.y==b.y) return a.id>b.id;
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int g[505],f[505][505];
int main(){
	n=read(); mod=read(); memset(l,0x3f,sizeof(l));
	for(int i=0;i<2*n;++i) for(int j=0;j<2*n;++j){
		v[i][j]=(n*n<=i*i+j*j)&&(i*i+j*j<=4*n*n);
		if(v[i][j]) l[i]=min(l[i],j),r[i]=j;
	}
	for(int i=0;i<n;++i) nd[++id].x=l[i]-1,nd[id].y=r[i],nd[id].id=i;
	for(int i=n;i<2*n;++i) nd[++id].x=r[i],nd[id].y=-1,nd[id].id=i;
	sort(nd+1,nd+1+2*n,jud);
	for(int i=1;i<=id;++i) g[i]=g[i-1]+(nd[i].y>=0);
	for(int tot=0;tot<=n;++tot){
		memset(f,0,sizeof(f)); f[0][0]=1;
		for(int i=0;i<id;++i) for(int j=0;j<=tot&&j<=i;++j){
			if(nd[i+1].y==-1) f[i+1][j]=add(f[i+1][j],1ll*f[i][j]*max(0,nd[i+1].x-(i-(g[i]-j))+1)%mod);
			else f[i+1][j]=add(f[i+1][j],1ll*f[i][j]*max(0,nd[i+1].y-(2*n-1-nd[i+1].id)-tot+j+1)%mod),
				f[i+1][j+1]=add(f[i+1][j+1],1ll*f[i][j]*max(0,nd[i+1].x-(i-(g[i]-j))+1)%mod);
		}
		ans=(ans+(tot&1?mod-1ll:1ll)*f[id][tot])%mod;
	}
	printf("%d\n",ans);
	return 0;
}