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 <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, mod;
long long S1[525], S2[525];
long long V[252525];
long long dp[525][525];
vector<int> R[525];

void init() {
	for (int i = 1; i <= 500; i++) {
		for (int j = i * i; j < (i + 1) * (i + 1); j++) V[j] = i;
	}
}

long long solve(int pos) {
	// [1] 初期化
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) dp[i][j] = 0;
	}

	// [2] 計算
	int cx = 0; dp[N][0] = 1;
	for (int i = N - 1; i >= 0; i--) {
		for (int j : R[i]) {
			cx++;
			for (int k = 0; k <= N; k++) {
				int s0 = k + cx;
				dp[i + 1][k] *= 1LL * max(0LL, 2LL + S2[j] - s0);
				dp[i + 1][k] %= mod;
			}
		}
		for (int j = 0; j <= N; j++) {
			if (dp[i + 1][j] == 0) continue;

			// 違反する場合
			int s1 = cx + j + 1;
			if (2LL + S1[i] - s1 >= 1) {
				dp[i][j + 1] += 1LL * (2LL + S1[i] - s1) * dp[i + 1][j];
				dp[i][j + 1] %= mod;
			}

			// 違反しない場合
			int s2 = N + pos + (N - i - j);
			if (2LL + S2[i] - s2 >= 1) {
				dp[i][j + 0] += 1LL * (2LL + S2[i] - s2) * dp[i + 1][j];
				dp[i][j + 0] %= mod;
			}
		}
	}

	long long val = dp[0][pos];
	for (int i = 2 * N - 1; i >= N; i--) {
		if (S2[i] <= N - 1) continue;
		int s3 = pos + (2 * N - i);
		val *= 1LL * max(0LL, 2LL + S2[i] - s3);
		val %= mod;
	}
	return val;
}

int main() {
	// ステップ 1. 入力
	init();
	cin >> N >> mod;

	// ステップ 2. 初期化
	for (int i = 0; i <= N - 1; i++) S1[i] = V[N * N - 1 - i * i];
	for (int i = 0; i <= 2 * N - 1; i++) S2[i] = min(2 * N - 1, V[4 * N * N - i * i]);
	for (int i = 2 * N - 1; i >= N; i--) {
		int border = -1;
		for (int j = N - 1; j >= 0; j--) {
			if (S1[j] >= S2[i]) { border = j; break; }
		}
		if (border >= 0) R[border].push_back(i);
	}

	// ステップ 3. DP
	long long Answer = 0;
	for (int i = 0; i <= N; i++) {
		long long val = solve(i);
		if (i % 2 == 0) Answer += val;
		if (i % 2 == 1) Answer -= val;
		Answer = (Answer + mod) % mod;
	}

	// ステップ 4. 出力
	cout << Answer << endl;
	return 0;
}