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>
using namespace std;

int Sqrt(int n) {
	int x = sqrt(n);
	while (x * x <= n) ++x;
	while (x * x > n) --x;
	return x;
}

int main() {
	int n, P;
	scanf("%d%d", &n, &P);
	vector<int> val(3 * n), id(3 * n);
	for (int i = 0; i < n; ++i)
		val[i] = Sqrt(n * n - i * i - 1) + 1;
	for (int i = 0; i < 2 * n; ++i)
		val[n + i] = min(2 * n - 1, Sqrt(4 * n * n - i * i)) + 1;
	for (int i = 0; i < 3 * n; ++i)
		id[i] = i;
	sort(id.begin(), id.end(), [&](int x, int y) { return val[x] < val[y] || (val[x] == val[y] && x > y); });
	int ans = 0;
	for (int k = 0; k <= n; ++k) {
		vector<int> f(k + 1);
		f[0] = 1;
		int cnt = 0;
		for (int i = 0; i < 2 * n; ++i) {
			if (id[i] < n) {
				for (int j = k; j >= 0; --j)
					if (f[j] || f[j - 1])
						f[j] = ((j == 0 ? 0 : 1ll * f[j - 1] * max(0, val[id[i]] - j + 1 - cnt)) + 1ll * f[j] * max(0, val[id[i] + n] - (n + k + n - 1 - id[i] - j))) % P;
			} else {
				for (int j = 0; j <= k; ++j)
					if (f[j]) f[j] = 1ll * f[j] * max(0, val[id[i]] - (cnt + j)) % P;
				++cnt;
			}
		}
		ans = (ans + (k & 1 ? -1 : 1) * f[k]) % P;
	}
	printf("%d\n", (ans + P) % P);
	return 0;
}
