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 <algorithm>
using namespace std;
#define mp make_pair
#define fi first
#define se second
typedef pair<int, int> pii;
const int MAXN = 500;
int N, M;
int add(int x, int y) {return (x + y) % M;}
int mul(int x, int y) {return 1LL*x*y % M;}
int sub(int x, int y) {return add(x, M-y);}
int f[MAXN + 5][MAXN + 5]; pii a[MAXN + 5];
int solve(int t) {
	int cnt1 = 0, cnt2 = 0;
	f[0][0] = 1;
	for(int i=0;i<2*N;i++) {
		if( a[i].se == 0 ) {
			for(int j=0;j<=cnt2;j++)
				f[i+1][j] = mul(f[i][j], a[i].fi - (cnt1 + j) + 1);
			cnt1++;
		}
		else {
			f[i+1][0] = 0;
			for(int j=0;j<=cnt2;j++)
				f[i+1][j+1] = mul(f[i][j], a[i].fi - (cnt1 + j) + 1);
			for(int j=0;j<=cnt2;j++)
				f[i+1][j] = add(f[i+1][j], mul(f[i][j], a[i].se - (N + cnt2 - j + t) + 1));
			cnt2++;
		}
	}
	return f[2*N][t];
}
int main() {
	scanf("%d%d", &N, &M);
	for(int i=0;i<N;i++) {
		a[i].fi = 0, a[i].se = 2*N - 1;
		while( a[i].fi*a[i].fi + i*i < N*N ) a[i].fi++; a[i].fi--; 
		while( a[i].se*a[i].se + i*i > 4*N*N ) a[i].se--;
	}
	for(int i=N;i<2*N;i++) {
		a[i].fi = 2*N - 1, a[i].se = 0;
		while( a[i].fi*a[i].fi + i*i > 4*N*N ) a[i].fi--;
	}
	sort(a, a + 2*N);
	int ans = 0;
	for(int i=N;i>=0;i--)
		ans = sub(solve(i), ans);
	printf("%d\n", ans);
}