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<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<list>
#include<map>
using namespace std;
#define ll long long
ll dp[505][505],sum,n,p,ans;
ll jian(ll x){
	return x<0?x+p:x;
}
ll add(ll x){
	return x>=p?x-p:x;
}
struct l1{
	ll dw,up,id;
}sid[200005];
ll cmp(l1 x,l1 y){
	ll tag1=(x.id<n),tag2=(y.id<n);
	ll d1,u1,d2,u2;
	if(tag1) d1=x.dw-1,u1=x.up;
	else d1=x.up,u1=x.dw-1;
	if(tag2) d2=y.dw-1,u2=y.up;
	else d2=y.up,u2=y.dw-1;
//	cout<<d1<<' '<<u1<<' '<<d2<<' '<<u2<<' '<<tag1<<' '<<tag2<<' '<<x.id<<' '<<y.id<<endl;
	if(d1!=d2) return d1<d2;
	if(u1!=u2) return u1<u2;
	return x.id>y.id;
}
ll solve(ll k){
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	sum=0;
	for(ll i=1;i<=2*n;i++){
//		cout<<sid[i].dw<<' '<<sid[i].up<<' '<<sid[i].id<<endl;
		for(ll t=0;t<=k;t++){
			if(sid[i].id>=n){
				ll qwq=sid[i].up+1-(i-1-(sum-t));
				dp[i][t]=(dp[i][t]+dp[i-1][t]*qwq)%p;
			}
			else{
				ll qwq=sid[i].up+1-(2*n-sid[i].id-1+k-t);
				dp[i][t]=(dp[i][t]+dp[i-1][t]*qwq)%p;
				if(t){
					qwq=sid[i].dw-(i-1-(sum-t+1));
					dp[i][t]=(dp[i][t]+dp[i-1][t-1]*qwq)%p;
				}
			}
		}
		sum+=sid[i].id<n;
	}
	return dp[2*n][k];
}
int main(){
	scanf("%lld%lld",&n,&p);
	for(ll i=0;i<=2*n-1;i++){
		sid[i+1].id=i;
		sid[i+1].dw=max((ll)ceil(sqrt(n*n-i*i)),0ll);
		sid[i+1].up=min((ll)floor(sqrt(4*n*n-i*i)),2*n-1);
	}
	sort(sid+1,sid+2*n+1,cmp);
	for(ll i=0;i<=n;i++){
		if(i&1) ans=jian(ans-solve(i));
		else ans=add(ans+solve(i));
	}
	printf("%lld",ans);
}