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 <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> L(2 * N), R(2 * N);
	for (int i = 0; i < 2 * N; ++i) {
		while (L[i] * L[i] + i * i < N * N) ++L[i];
		while (R[i] < 2 * N && R[i] * R[i] + i * i <= 4 * N * N) ++R[i];
	}
	int ans = 0;
	for (int i = 0; i <= N; ++i) {
		vector<vector<int> > dp(N + 1, vector<int>(i + 1));
		dp[N][0] = 1;
		int ptr = 2 * N, anti = 0;
		for (int j = N - 1; j >= 0; --j) {
			while (R[ptr - 1] < L[j]) {
				--ptr;
				for (int k = 0; k <= N - j - 1 && k <= i; ++k) {
					dp[j + 1][k] = 1LL * dp[j + 1][k] * max(R[ptr] - (k + anti), 0) % M;
				}
				++anti;
			}
			for (int k = 0; k <= N - j - 1 && k <= i; ++k) {
				if (k != i) dp[j][k + 1] = (dp[j][k + 1] + 1LL * dp[j + 1][k] * max(L[j] - (k + anti), 0)) % M;
				dp[j][k] = (dp[j][k] + 1LL * dp[j + 1][k] * max(R[j] - (2 * N - j + (i - k) - 1), 0)) % M;
			}
		}
		int sub = dp[0][i];
		while (ptr > N) {
			--ptr;
			sub = 1LL * sub * max(R[ptr] - (i + anti), 0) % M;
			++anti;
		}
		if (i % 2 == 0) ans = (ans + sub) % M;
		else ans = (ans - sub + M) % M;
	}
	cout << ans << endl;
	return 0;
}
