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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define clr(x) memset(x,0,sizeof x)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef double ld;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=505;
struct node{
	int p,id;
	friend bool operator < (node a,node b){
		return a.p<b.p||a.p==b.p&&a.id>b.id;
	}
}a[N];
int l[N],r[N],f[N][N];
int n,mod,ans;

void add(int &x,int y){
	x=(x+y>=mod?x+y-mod:x+y);
}
int mul(int x,int y){
	return (ll)x*y%mod;
}

int main(){
	read(n),read(mod);
	rep(i,0,2*n-1){
		r[i]=min(2*n-1,(int)sqrt(4*n*n-i*i));
		if(i>=n) a[i+1]=(node){r[i],i};
		else{
			l[i]=ceil(sqrt(n*n-i*i));
			a[i+1]=(node){l[i]-1,i};
		}
	}
	sort(a+1,a+n*2+1);
	rep(k,0,n){
		clr(f),f[0][0]=1;
		int c0=0,c1=0;
		rep(i,1,n*2){
			int p=a[i].id;
			rep(j,0,min(n-k,i-1))
				if(f[i-1][j])
					if(p<n){
						add(f[i][j+1],mul(f[i-1][j],1+r[p]-(n+k+j)));
						add(f[i][j],mod-mul(f[i-1][j],l[p]-(c0+c1-j)));
					}
					else{
						add(f[i][j],mul(f[i-1][j],1+r[p]-(c0+c1-j)));
					}
			if(p>=n)c1++;
			else c0++;
		}
		ans=(ans+f[n*2][n-k])%mod;
	}
	cout<<ans<<endl;
	return 0;
}