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;

const int maxn=503;

ll n,m,dp[maxn][maxn];

int f(int i){
	static int rt=2*n-1;
	while(rt>=0&&i*i+rt*rt>4*n*n)
		--rt;
	return rt+1;
}
int g(int i){
	static int rt=2*n-1;
	while(rt>=0&&i*i+rt*rt>=n*n)
		--rt;
	return rt+1;
}

int main(){
	vector<pair<ll,ll> > a;
	scanf("%lld%lld",&n,&m);
//	printf("%lld ^^\n",m);
	for(ll i=0;i<2*n;++i){
		if(i<n)a.push_back(make_pair(g(i),f(i)));
		else a.push_back(make_pair(f(i),0));
	}
	ll c1,c2,ans=0;
	sort(a.begin(),a.end());
//	for(ll i=0;i<a.size();++i)
//		printf("(%lld %lld)\n",a[i].first,a[i].second);
	for(ll k=0;k<=n;++k){
//		printf("%d : \n",k);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		c1=c2=0;
		for(ll i=0;i<a.size();++i){
			for(ll j=0;j<=k;++j){
				if(a[i].second==0){
					dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].first-c1-j)%m)%m;
//					printf("%lld %lld %d %d %d^\n",dp[i][j],a[i].first-c1-j,a[i].first,c1,j);
				}else{
					if(j<k)
						dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(a[i].first-c1-j)%m)%m;
					dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].second-n-k-(c2-j))%m)%m; 
				}
//				printf("%lld ",dp[i][j]);
			}
			if(a[i].second==0)++c1;
			else ++c2;
//			puts("");
		}
//		return 0;
		if(k%2)ans=(ans-dp[2*n][k]+m)%m;
		else ans=(ans+dp[2*n][k])%m;
//		printf("%lld !\n",ans);
//		puts("");
	}
	printf("%lld\n",ans);
	return 0;
}

