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>

const int N = 505;
using LL = long long;
int dp[N][N], n, mod, l[N], r[N];
struct node { int val, id, typ; } data[N];
void reduce(int &x) { x += x >> 31 & mod; }
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> mod;
	for (int i = 0; i < n; ++i)
		l[i] = std::ceil(std::sqrt(n * n - i * i)), r[i] = std::sqrt(4 * n * n - i * i) + 1;
	for (int i = n; i < n + n; ++i)
		r[i] = std::sqrt(4 * n * n - i * i) + 1;
	r[0] = 2 * n;
	for (int i = 0; i < n; ++i)
		data[i] = {l[i], i, 0};
	for (int i = n; i < 2 * n; ++i)
		data[i] = {r[i], i, 1};
	std::sort(data, data + n + n, [] (node a, node b) { return a.val != b.val ? a.val < b.val : r[a.id] < r[b.id]; });
	int ans = 0;
	for (int k = 0; k <= n; ++k) {
		std::memset(dp, 0, sizeof dp);
		dp[0][0] = 1; int bsum = 0, asum = 0;
		for (int i = 0; i < n * 2; ++i) {
			for (int j = 0; j <= k; ++j) {
				if (data[i].typ == 0) {
					// choose a
					reduce(dp[i + 1][j + 1] -= (LL) dp[i][j] * (data[i].val - j - bsum) % mod);
					// choose c
					reduce(dp[i + 1][j] += (LL) dp[i][j] * (r[data[i].id] - k - n - (asum - j)) % mod - mod);
				} else {
					// choose b
					reduce(dp[i + 1][j] += (LL) dp[i][j] * (data[i].val - j - bsum) % mod - mod);
				}
			}
			if (data[i].typ == 1) ++bsum;
			else ++asum;
		}
		// std::cout << dp[4][0] << std::endl;
		reduce(ans += dp[n * 2][k] - mod);
	}
	std::cout << ans << '\n';
	return 0;
}
