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<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
struct Node
{
	int l,r;
}a[505];
int n;
ll MOD,f[505][505],ans;
bool cmp(Node a,Node b)
{
	if(a.l==0&&b.l==0)return a.r<b.r;
	if(a.l==0)return a.r<=b.l-1;
	if(b.l==0)return a.l-1<b.r;
	return a.l<b.l||(a.l==b.l&&a.r<b.r);
}
int main()
{
	scanf("%d%lld",&n,&MOD);
	int nowr=2*n-1,nowl=n;
	for(int i=0;i<2*n;i++)
	{
		while(i*i+nowr*nowr>4*n*n)nowr--;
		while(nowl>=0&&i*i+nowl*nowl>=n*n)nowl--;
		a[i].r=nowr;
		a[i].l=nowl+1;
	}
	sort(a,a+2*n,cmp);
	for(int x=0;x<=n;x++)
	{
		memset(f,0,sizeof(f));
		f[0][0]=1;
		int num=0;
		for(int i=0;i<2*n;i++)
		{
			for(int j=0;j<=x;j++)
			{
				if(f[i][j]==0)continue;
				f[i][j]%=MOD;
				if(a[i].l==0)f[i+1][j]+=f[i][j]*(a[i].r+1-j-num);
				else
				{
					f[i+1][j]+=f[i][j]*(a[i].r+1-i-(n-num)-(x-j));
					f[i+1][j+1]+=f[i][j]*(a[i].l-j-num);
				}
			}
			if(a[i].l==0)num++;
		}
		if(x&1)ans-=f[2*n][x];
		else ans+=f[2*n][x];
	}
	ans%=MOD;
	if(ans<0)ans+=MOD;
	printf("%lld\n",ans);
	return 0;
}