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>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=502;
int n,M,i,j,k,L[N],R[N],o,t;
ll f[N][N],Ans;
struct Uzi{
    int id,u,v;
    bool operator<(const Uzi &k)const{
        if(u!=k.u)
            return u<k.u;
        return v<k.v;
    }
}p[N];
void init(){
    scanf("%d%d",&n,&M);
    for(i=0;i<2*n;i++){
        L[i]=R[i]=-1;
        for(j=0;j<2*n;j++)
            if(n*n<=i*i+j*j&&i*i+j*j<=n*n*4){
                if(L[i]==-1)
                    L[i]=j;
                R[i]=j;
            }
        if(i<n)
            p[i+1]=(Uzi){i,L[i]-1,R[i]};
        else
            p[i+1]=(Uzi){i,R[i],L[i]};
    }
    sort(p+1,p+2*n+1);
}
void work(){
    for(k=0;k<=n;k++){
        memset(f,0,sizeof(f));
        f[0][0]=1;
        t=0;
        for(i=1;i<=n*2;i++){
            o=p[i].id;
            for(j=0;j<=k;j++){
                if(o>=n){
                    f[i][j]=f[i-1][j]*(R[o]+1-t-j)%M;
                }
                else{
                    f[i][j]=f[i-1][j]*(R[o]+1-(2*n-1-o)-(k-j))%M;
                    if(j&&L[o]>t+j-1)
                        f[i][j]=(f[i][j]+f[i-1][j-1]*(L[o]-t-j+1))%M;
                    
                }
            }
            if(o>=n)
                t++;
        }
        Ans=(Ans+f[n*2][k]*(k%2?-1:1)+M)%M;
    }
    printf("%lld",Ans);
}
int main(){
    init();
    work();
    return 0;
}