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<cstring>
#define N 505
int a[N],b[N],f[N],i,j,m,n,o,p,x;
int main()
{
    scanf("%d%d",&n,&m);
    for(*a=n-1,i=1;i<n;i++)for(a[i]=a[i-1];n*n<=a[i]*a[i]+i*i;a[i]--);
    for(*b=(n<<=1)-1,i=1;i<n;i++)for(b[i]=b[i-1];n*n<b[i]*b[i]+i*i;b[i]--);
    for(j=0;j<=n>>1;x=j&1?(m+x-f[j])%m:(x+f[j])%m,j++)for(memset(f+1,0,j<<2),*f=1,o=n>>1,p=n;o||(n>>1)<p;)
    if(!o||(n>>1)<p&&b[p-1]<=a[o-1])for(p--,i=0;i<=(n>>1)-o&&i<=j;i++)f[i]=f[i]*(b[p]+2ll-n+p-i)%m;
    else for(i=(i=(n>>1)-o--)<j?i:j;i>=0;i--)f[i+1]=(f[i+1]+f[i]*(a[o]+1ll-n+p-i))%m,f[i]=f[i]*(b[o]+2ll-n+o-j+i)%m;
    return 0*printf("%d\n",x);
}