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<algorithm>
using namespace std;
int n, Mod, A[510], B[510], R[510];
long long D[510][510];
struct point {
	int a, c;
	bool operator <(const point &p)const {
		return c != p.c ? c<p.c : a>p.a;
	}
}w[510];
long long Do(int K) {
	int i, j;
	for (i = 0; i <= n + n; i++)for (j = 0; j <= K; j++)D[i][j] = 0;
	D[0][0] = 1;
	int c = 0;
	for (i = 1; i <= n + n; i++) {
		int x = w[i].a;
		if (x <= n) {
			for (j = 0; j <= K; j++) {
				D[i][j + 1] = (D[i][j + 1] + D[i - 1][j] * (w[i].c - j - c))%Mod;
				D[i][j] = (D[i][j] + D[i - 1][j] * max(B[x] - n - (i-1-c) - (K - j), 0)) % Mod;
			}
		}
		else {
			for (j = 0; j <= K; j++) {
				D[i][j] = (D[i][j] + D[i - 1][j] * (w[i].c - j - c)) % Mod;
			}
			c++;
		}
	}
	return D[2*n][K];
}
int main() {
	scanf("%d%d", &n, &Mod);
	int i, j;
	for (i = 0; i < 2*n; i++) {
		for (j = 0; j < 2 * n; j++) {
			if (i*i + j * j < n*n)A[i+1] = j + 1;
			if (i*i + j * j <= 4*n*n)B[i+1] = j + 1;
		}
	}
	for (i = 1; i <= 2 * n; i++) {
		w[i].a = i;
		w[i].c = A[i];
		if (i > n)w[i].c = B[i];
	}
	sort(w + 1, w + n + n + 1);
	long long res = 0;
	for (i = 0; i <= n; i++) {
		R[i] = Do(i);
		if (i % 2==0)res += R[i];
		else res += Mod - R[i];
	}
	printf("%lld\n", res%Mod);
}