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>

typedef long long ll;
const int N = 508;

int mod;
int n;
int l[N], u[N], left[N], right[N];
int stdo[N], f[N][N];

int work(int K) {
	int i, j, k, id; **f = 1;
	for (i = 0; i < 2 * n; ++i)
		if ((id = stdo[i]) < n) {
			for (j = left[i], k = n + K - 1; j >= 0; --j, ++k)
				f[i + 1][j + 1]	= (f[i][j + 1] * ll(u[id] - k) + f[i][j] * ll(l[id] - right[i] - j)) % mod;
			f[i + 1][0] = f[i][0] * ll(u[id] - k) % mod;
		} else for (j = 0; j <= left[i]; ++j) f[i + 1][j] = f[i][j] * ll(u[id] - right[i] - j) % mod;
	return f[2 * n][K];
}

int main() {
	int i; ll ans = 0;
	scanf("%d%d", &n, &mod);
	for (i = 0; i < 2 * n; ++i) l[i] = u[i] = 1 + (int)sqrt(4 * n * n - i * i), stdo[i] = 2 * n - i - 1;
	for (i = 0; i < n; ++i) l[i] = ceil(sqrt(n * n - i * i)); *u = 2 * n;
	std::inplace_merge(stdo, stdo + n, stdo + 2 * n, [] (const int x, const int y) {return l[x] < l[y];});
	for (i = 0; i < 2 * n; ++i)
		left[i + 1] = left[i], right[i + 1] = right[i], stdo[i] < n ? ++left[i + 1] : ++right[i + 1];
	for (i = 0; i <= n; ++i) i & 1 ? ans -= work(i) : ans += work(i);
	ans %= mod, printf("%d\n", int(ans + (ans >> 63 & mod)));
	return 0;
}