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<stdio.h>
int num1[512],num2[512];
int wz[512];
int dp[512];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int now=(n<<1)-1;
	for(int i=0;i<n;i++)
	{
		while(i*i+now*now>=n*n)
		{
			now--;
		}
		num1[now]++;
	}
	now=(n<<1)-1;
	for(int i=0;i<(n<<1);i++)
	{
		while(i*i+now*now>(n<<1)*(n<<1))
		{
			now--;
		}
		if(i<n)
		{
			wz[i]=now;
		}
		else
		{
			num2[now]++;
		}
	}
	int ans=0;
	for(int k=0;k<=n;k++)
	{
		for(int i=0;i<=k;i++)
		{
			dp[i]=0;
		}
		dp[0]=1;
		int now=n,numb=0;
		for(int i=0;i<(n<<1);i++)
		{
			int val=num1[i];
			while(val--)
			{
				now--;
				for(int j=k;j>=0;j--)
				{
					if(j<k&&i-j-numb+1>0)
					{
						dp[j+1]+=(long long)dp[j]*(i-j-numb+1)%m;
						if(dp[j+1]>=m)
						{
							dp[j+1]-=m;
						}
					}
					if(wz[now]-(n+n-1-now)-(k-j)+1>0)
					{
						dp[j]=(long long)dp[j]*(wz[now]-(n+n-1-now)-(k-j)+1)%m;
					}
					else
					{
						dp[j]=0;
					}
				}
			}
			val=num2[i];
			while(val--)
			{
				for(int j=0;j<=k;j++)
				{
					if(i-j-numb+1>0)
					{
						dp[j]=(long long)dp[j]*(i-j-numb+1)%m;
					}
					else
					{
						dp[j]=0;
					}
				}
				numb++;
			}
		}
		if(k&1)
		{
			ans-=dp[k];
			if(ans<0)
			{
				ans+=m;
			}
		}
		else
		{
			ans+=dp[k];
			if(ans>=m)
			{
				ans-=m;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}