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;
const int MAXN = 255;
const int MAXM = 505;
const int INF  = 1e9;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, m, Q, P;
int dp[MAXM][MAXN];
pair <int, int> a[MAXM];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	read(n), read(Q), P = INF / Q * Q;
	int p = 2 * n - 1, q = 2 * n - 1;
	for (int i = 0; i <= 2 * n - 1; i++) {
		while (i * i + p * p > (2 * n) * (2 * n) && p >= 0) p--;
		while (i * i + q * q >= n * n && q >= 0) q--;
		if (q == -1) a[++m] = make_pair(p + 1, 0);
		else a[++m] = make_pair(q + 1, p + 1);
	}
	sort(a + 1, a + m + 1);
	int ans = 0;
	for (int k = 0; k <= n; k++) {
		memset(dp, 0, sizeof(dp)), dp[0][0] = 1;
		for (int i = 1, f = 0, g = 0; i <= m; f += a[i].second != 0, g += a[i].second == 0, i++)
		for (int j = 0; j <= k; j++) {
			int tmp = dp[i - 1][j];
			if (a[i].second == 0) update(dp[i][j], 1ll * tmp * (a[i].first - j - g) % P);
			else {
				if (j != k) update(dp[i][j + 1], 1ll * tmp * (a[i].first - j - g) % P);
				update(dp[i][j], 1ll * tmp * (a[i].second - k - n - (f - j)) % P);
			}
		}
		int now = dp[m][k];
		if (k & 1) update(ans, P - now);
		else update(ans, now);
	}
	writeln(ans % Q);
	return 0;
}