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>
using namespace std;
typedef long long ll;
const int N=305;
int f[2][N][N];
ll l[N*2],r[N*2],n,mo;
int d[N*2];
void move(int &a,ll b){
	a=(a+b)%mo;
}
int main(){
	cin>>n>>mo;
	for (int i=0;i<2*n;i++){
		l[i]=2*n;
		for (int j=0;j<2*n;j++){
			if (n*n<=i*i+j*j&&i*i+j*j<=4*n*n){
				l[i]=min(l[i],(ll)j);
				r[i]=max(r[i],(ll)j);
			}
		}
	}
	int p=n-1,q=2*n-1;
	for (int i=1;i<=2*n;i++){
		if (q<n||p>=0&&l[p]<=r[q])d[i]=p--;
		else d[i]=q--;
	}
	for (int i=0;i<=n;i++)f[0][0][i]=i&1?-1:1;
	int _=0,cnt=0;
	for (int i=1;i<=2*n;i++){
		int x=d[i];_^=1;
		memset(f[_],0,sizeof f[_]);
		for (int j=0;j<=n;j++)
			for (int k=0;j+k<=n;k++){
				if (x>=n)
					move(f[_][j][k],f[!_][j][k]*(r[x]+1-j-cnt));
				else {
					move(f[_][j][k],f[!_][j][k]*(r[x]+1-(i-1+k+n-cnt)));
					if (k)move(f[_][j+1][k-1],f[!_][j][k]*(l[x]-j-cnt));
				}
			}
		cnt+=x>=n;
	}
	int ans=0;
	for (int i=0;i<=n;i++)move(ans,f[_][i][0]);
	cout<<(ans%mo+mo)%mo<<endl;
}