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;
typedef bool boolean;

#define pii pair<int, int>
#define ll long long

const int N = 505;

int n, n2, Mod;
pii a[N];
int cnt[N];
int dp[2][N];

int main() {
	scanf("%d%d", &n, &Mod);
	n2 = n << 1;
	int p1 = 0, p2 = 0, N4 = 4 * n * n, N2 = n * n;
	for (int i = n2 - 1; ~i; i--) {
		while (p1 < n2 && p1 * p1 <= N4 - i * i)
			p1++;
		while (p2 * p2 < N2 - i * i)
			p2++;
		if (p2) {
			a[i] = pii(p2, p1);
		} else {
			a[i] = pii(p1, 0);
		}
	}
	sort(a, a + n2);
	cnt[0] = 0;
	for (int i = 0; i < n2; i++)
		cnt[i + 1] = cnt[i] + !a[i].second;
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		int cur = 0;
		memset(dp[0], 0, sizeof(dp[0]));
		dp[0][0] = 1;
		for (int j = 0; j < n2; j++) {
			memset(dp[cur ^= 1], 0, sizeof(dp[0]));
			for (int k = 0; k <= i; k++) {
				if (!a[j].second) {
					dp[cur][k] = (dp[cur][k] + 1ll * (a[j].first - k - cnt[j]) * dp[cur ^ 1][k]) % Mod;
				} else {
					dp[cur][k + 1] = (dp[cur][k + 1] - 1ll * (a[j].first - k - cnt[j]) * dp[cur ^ 1][k]) % Mod;
					dp[cur][k] = (dp[cur][k] + 1ll * (a[j].second - (n + i + j - cnt[j] - k)) * dp[cur ^ 1][k]) % Mod;
				}
			}
		}
		ans += dp[cur][i];
	}
	ans %= Mod;
	(ans < 0) && (ans += Mod);
	printf("%d\n", (int) ans);
	return 0;
}
