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>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int sqt[250005];
int n, m;
int tot[255];
int dp[255][255];

int solve(int ct)
{
	int ret = 0;
	dp[0][0] = 1;
	int cur = 0;
	for(int i = n - 1; i >= 0; i --) {
		int lb = sqt[n * n - i * i - 1] + 1, rb = sqt[4 * n * n - i * i] + 1;
		for(int j = 0; j <= n; j ++) dp[n - i][j] = dp[n - i - 1][j];
		while(cur < n && tot[cur] <= lb) {
			for(int j = 0; j <= n; j ++) dp[n - i][j] = 1LL * dp[n - i][j] * (tot[cur] - cur - j + m) % m;
			cur ++;
		}
		for(int j = n; j >= 0; j --) {
			dp[n - i][j] = 1LL * dp[n - i][j] * (rb - 2 * n - ct + i + 1 + j + m) % m;
			if(j > 0) dp[n - i][j] = (dp[n - i][j] + 1LL * dp[n - i][j - 1] * (lb - cur - j + 1 + m)) % m;
		}
	}
	while(cur < n) {
		for(int j = 0; j <= n; j ++) dp[n][j] = 1LL * dp[n][j] * (tot[cur] - cur - j + m) % m;
		cur ++;
	}
	return dp[n][ct];
}

int main()
{
	scanf("%d%d", &n, &m);
	rep(i, 2 * n) for(int j = i * i; j < (i + 1) * (i + 1); j ++)
	sqt[j] = i;
	sqt[4 * n * n] = 2 * n - 1;
	int ans = 0;
	for(int t = 2 * n - 1; t >= n; t --)
	tot[2 * n - 1 - t] = sqt[4 * n * n - t * t] + 1;
	for(int t = 0; t <= n; t ++)
	if(t & 1) ans = (ans - solve(t) + m) % m;
	else ans = (ans + solve(t)) % m;
	printf("%d\n", ans);
	return 0;
}