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<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#define cri const int
#define ll long long
using namespace std;
int dp[502][502],ans;
pair<int,int>f[502];
inline int read(int x=0){ scanf("%d",&x);return x; }
int main(){
	cri n=read(),mod=read();
	for(int i=0;i<n+n;i++){
		if(i>=n) f[i]=make_pair((int)sqrt(4*n*n-i*i)+1,0);
		else f[i]=make_pair((int)(sqrt(n*n-i*i-1e-7))+1,(int)sqrt(4*n*n-i*i)+(i!=0));
	}
	sort(f,f+n+n);
	for(int k=0;k<=n;k++){
		int c1=0,c2=0;
		memset(dp,0,sizeof dp);
		dp[0][0]=1;
		for(int i=0;i<n+n;!f[i].second?c1++:c2++,i++)
			for(int j=0;j<=k;j++){
				if(!f[i].second) dp[i+1][j]=(dp[i+1][j]+1ll*dp[i][j]*(f[i].first-j-c1))%mod;
				else{
					if(j<k) dp[i+1][j+1]=(dp[i+1][j+1]+1ll*dp[i][j]*(f[i].first-j-c1))%mod;
					dp[i+1][j]=(dp[i+1][j]+1ll*dp[i][j]*(f[i].second-n-k-(c2-j)))%mod;
				}
			}
		if(k&1) ans=(ans-dp[n+n][k]+mod)%mod;
		else ans=(ans+dp[n+n][k])%mod;
	}
	cout<<ans<<endl;
}