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<cctype>
#include<algorithm>

typedef long long LL;

int read(){
    int w=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    for(;isdigit(ch);ch=getchar())w=w*10+(ch^48);
    return w;
}
int max(int x,int y){return x>y?x:y;}

const int N=505;

int n,mod;
int l[N],r[N],v[N],v2[N];
LL f[N][N];
int sorted[N];
LL ans;

bool cmp(int x,int y){
    if(v[x]==v[y])return v2[x]<v2[y];
    return v[x]<v[y];
}

int main(){
    n=read();mod=read();
    int topl=n*n-1,topr=2*n*2*n;
    for(int i=2*n-1;i>=0;--i){
        for(int j=0;j<2*n;++j){
            if(i*i+j*j<=topr){
                r[i]=j;
            }
        }
        for(int j=0;j<2*n;++j){
            if(i*i+j*j<=topl){
                l[i]=j;
            }
        }
        sorted[i] = i;
        v[i] = (i < n ? l[i] : r[i]);
        v2[i] = (i < n ? r[i] : 0);
    }
    std::sort(sorted,sorted+2*n,cmp);
    for(int k=0,s=1;k<=n;++k,s*=-1){
        f[0][0] = 1;
        int cnt = 0;
        for(int i=1;i<=2*n;++i){
            int w = sorted[i-1];
            if(w<n){
                f[i][0] = (f[i-1][0] * (r[w] + 1 - (2*n-1 - w + k))) % mod;
                for(int j=1;j<=k;++j){
                    f[i][j] = (f[i-1][j-1] * (l[w] + 1 - (i - 1 - (cnt - (j - 1))))
                              +f[i-1][j] * (r[w] + 1 - (2*n-1 - w + (k - j)))) % mod;
                }
                ++cnt;
            }else{
                for(int j=0;j<=k;++j){
                    f[i][j] = (f[i-1][j] * (r[w] + 1 - (i - 1 - (cnt - j)))) % mod;
                }
            }
        }
        ans = (ans + s*f[2*n][k] + mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}
