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
#define N 510
using namespace std;
struct Info{int l,r;}a[N];
ll n,mo,ans,dp[N][N];
bool c1(const Info &a,const Info &b){if (a.l!=b.l) return a.l<b.l;return a.r<b.r;}
int main(){
	cin>>n>>mo;
	for (int i=0;i<n;i++){
		for (int j=n+n-1;j>=0;j--)if (i*i+j*j>=n*n)a[i].l=j;
		for (int j=0;j<n+n;j++)if (i*i+j*j<=n*n*4)a[i].r=j;
		a[i].r++;
	}
	for (int i=n;i<n+n;i++){
		a[i].r=-1;
		for (int j=0;j<n+n;j++)if (i*i+j*j<=n*n*4)a[i].l=j;
		a[i].l++;
	}
	sort(a,a+n+n,c1);
	for (int k=0;k<=n;k++){
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for (int i=0;i<n+n;i++){
			for (int j=0;j<=k;j++){
				if ((a[i].l-i+j)>0)dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i].l-i+j))%mo;
				if ((a[i].r-n-n+(k-j))>0)dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j]*(a[i].r-n-n+(k-j)))%mo;
			}
		}
		if ((n-k)%2)ans=(ans+mo-dp[n+n][k])%mo;else ans=(ans+dp[n+n][k])%mo;
	}
	cout<<ans<<endl;
	return 0;
}