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 n, tot, mod, ans;

struct data {
	int l, r;

	bool operator < (const data &t) const {
		int vl = l ? l : r, vr = t.l ? t.l : t.r;
		if (vl != vr) return vl < vr;
		vl = l ? r : l, vr = t.l ? t.r : t.l;
		return vl < vr;
	}
}a[501];
int f[600][600];

inline void addto(int &x, int y) {
	x += y;
	if (x < 0) x += mod;
	if (x >= mod) x -= mod;
}

int main() {
	scanf("%d%d", &n, &mod);
	n *= 2;
	for (int i = 0; i < n; ++i) {
		int l = n, r = 0;
		for (int j = 0; j < n; ++j)
			if (i * i + j * j >= n * n / 4 && i * i + j * j <= n * n) {
				l = min(l, j); r = max(r, j);
			}
		a[i] = (data){l, r + 1};
	}
	sort(a, a + n);
	for (int i = 0; i < n; ++i)
		if (!a[i].l) ++tot;
	for (int i = 0; i <= n; ++i) {
		memset(f, 0, sizeof f);
		f[0][0] = 1;
		int cnt = 0;
		for (int j = 0; j < n; ++j) {
			for (int k = 0; k <= j; ++k) {
				if (a[j].l) {
					addto(f[j + 1][k + 1], 1ll * f[j][k] * (a[j].l - (cnt + k)) % mod);
					addto(f[j + 1][k], 1ll * f[j][k] * (a[j].r - (i + j - k + tot - cnt)) % mod);
				} else {
					addto(f[j + 1][k], 1ll * f[j][k] * (a[j].r - (cnt + k)) % mod);
				}
			}
			cnt += !a[j].l;
		}
		assert(cnt == tot);
		if (i & 1) addto(ans, -f[n][i]);
		else addto(ans, f[n][i]);
	}
	printf("%d", ans);
}
