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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 520
using namespace std;
int n,mod,ans,f[maxn][maxn];
struct point{
	int l,r,num,pos;
	friend bool operator <(point a,point b)
	{
		return a.pos<b.pos;
	}
}a[maxn];
int main()
{
	scanf("%d%d",&n,&mod);
	for(int i=0;i<2*n;i++)
	{
		a[i].num=i; a[i].r=min(2*n-1,(int)floor(sqrt(4*n*n-i*i)));
		if(i<n) a[i].l=ceil(sqrt(n*n-i*i)),a[i].pos=a[i].l-1;
		else a[i].pos=a[i].r;
	}
	sort(a,a+2*n);
	int ans=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=2*n;k++) f[j][k]=0;
		f[0][0]=1; int c1=0;
		for(int j=0;j<2*n;j++)
		{
			c1+=(a[j].num<n);
			for(int k=0;k<=min(c1,i);k++)
				if(a[j].num<n){
					f[j+1][k]=(f[j+1][k]+1ll*f[j][k]*(a[j].r+1-(2*n-1-a[j].num+i-k)))%mod;
					f[j+1][k+1]=(f[j+1][k+1]+1ll*f[j][k]*(a[j].pos+1-(j-(c1-k-1))))%mod;
				}
				else f[j+1][k]=1ll*f[j][k]*(a[j].pos+1-(j-(c1-k)))%mod;
		}
		if(i&1) ans=(0ll+ans-f[2*n][i]+mod)%mod;
		else ans=(ans+f[2*n][i])%mod;
	}
	printf("%d\n",ans);
}