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 <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=505;

int n,Mo,f[N][N];

struct P{int l,r,id;}a[N];

bool cmp(P a,P b) {
	int ax,ay,bx,by;
	if (a.id<n) ax=a.l,ay=a.r;else ax=a.r,ay=0;
	if (b.id<n) bx=b.l,by=b.r;else bx=b.r,by=0;
	if (ax!=bx) return ax<bx;
	return ay<by;
}

int main() {
	scanf("%d%d",&n,&Mo);
	fo(i,0,(n<<1)-1) {
		a[i].l=i<n?ceil(sqrt(n*n-i*i))-1:0;
		a[i].r=min((int)sqrt(4*n*n-i*i),(n<<1)-1);
		a[i].id=i;
	}
	sort(a,a+(n<<1),cmp);
	int ans=0;
	fo(k,0,n) {
		fo(i,1,(n<<1)) fo(j,0,min(i,k)) f[i][j]=0;
		f[0][0]=1;int t1=0,t2=0;
		fo(i,1,n<<1) 
			if (a[i-1].id>=n) {
				fo(j,0,min(i,k)) f[i][j]=(ll)f[i-1][j]*(a[i-1].r+1-(t2+j))%Mo;
				t2++;
			} else {
				fo(j,1,min(i,k)) f[i][j]=(ll)f[i-1][j-1]*(a[i-1].l+1-(t2+j-1))%Mo;
				fo(j,0,min(i,k)) (f[i][j]+=(ll)f[i-1][j]*(a[i-1].r+1-(n+t1+(k-j)))%Mo)%=Mo;
				t1++;
			}
		(ans+=(k&1?-1:1)*f[(n<<1)][k])%=Mo;
	}
	printf("%d\n",(ans+Mo)%Mo);
	return 0;
}