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>
#define MN 250
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,mod,mx[MN*2+5],mx2[MN*2+5],f[MN*2+5][MN+5],ans,S[MN*2+5],num;
inline void R(int&x,int y){(x+=y)>=mod?x-=mod:0;}
inline int OP(int x){return (x&1)?mod-1:1;}
int main()
{
    n=read();mod=read();
    for(int i=0;i<2*n;++i) mx[i]=int(sqrt(4*n*n-i*i)+1e-9);
    --mx[0];
    for(int i=0;i<=n;++i) mx2[i]=int(sqrt(n*n-i*i-1)+1e-9);
    for(int i=2*n-1,j=n;i>n||j>=0;)
        if(j<0||(i>n&&mx[i]<=mx2[j])) S[++num]=i--;
        else S[++num]=j--;
    for(int t=0;t<=n+1;++t)
    {
        int k=0;memset(f,0,sizeof(f));f[0][0]=1;
        for(int i=1;i<=num;S[i++]>n?++k:0) for(int j=0;j<=t;++j) if(f[i-1][j])
        {
            if(S[i]>n)
            {
                if(mx[S[i]]>=j+k) R(f[i][j],1LL*f[i-1][j]*(mx[S[i]]-(j+k)+1)%mod);
            }
            else
            {
                if(mx2[S[i]]>=j+k) R(f[i][j+1],1LL*f[i-1][j]*(mx2[S[i]]-(j+k)+1)%mod);
                if(mx[S[i]]-(2*n-S[i]-1+(t-j))>=0) R(f[i][j],1LL*f[i-1][j]*(mx[S[i]]-(2*n-S[i]-1+(t-j))+1)%mod);
            }
        }
        ans=(ans+1LL*OP(t)*f[num][t])%mod;
    }
    cout<<ans;
    return 0;
}