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 ll long long
using namespace std;
int f[510][510],n,mod,a[510],b[510];
ll ans;
void upd(int&a,ll b){a=(a+b)%mod;}
int main(){
	cin>>n>>mod;
	for(int i=0;i<2*n;i++){
		a[i]=b[i]=-1;
		for(int j=0;j<2*n;j++)
			if(j*j+i*i<=4*n*n) b[i]=j;
		for(int j=2*n-1;~j;j--)
			if(j*j+i*i>=n*n) a[i]=j;
	}
	for(int k=0;k<=2*n;k++){
		memset(f,0,sizeof(f));f[0][0]=1;
		int s1=0,s2=0,k1=n-1,k2=2*n-1;
		for(int i=0;i<2*n;i++){
			int now;
			if(k2<n||k1>=0&&a[k1]<b[k2]+1) now=k1--,s1++;
			else now=k2--,s2++;
			for(int j=0;j<=k&&j<=i;j++){
				if(now<n){
					upd(f[i+1][j+1],1ll*f[i][j]*(a[now]-j-s2));
					upd(f[i+1][j],1ll*f[i][j]*(b[now]+1-k-n-s1+j+1));
				}
				else upd(f[i+1][j],1ll*f[i][j]*(b[now]+1-j-s2+1));
			}
		}
		ans=(ans+(k&1?-1:1)*f[2*n][k])%mod;
	}
	cout<<(ans+mod)%mod<<'\n';
	return 0;
}
