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;

#define N 255
typedef pair<int, int> pii;

pii f[N*3];
int n, m;

int dp[N<<1][N];

typedef long long ll;

void add(int &a, ll b) {
	a = (a + b) % m;
}

int main() {
	cin>>n>>m;
	for (int i = 0; i < n; i ++) f[i+1] = pii(sqrt(n * n - 1 - i * i) + 1, -i);
	for (int i = 0; i < 2 * n; i ++) f[n+i+1] = pii(min(2 * n - 1, (int)sqrt(4 * n * n - i * i)) + 1, 1);
	sort(f + 1, f + n * 3 + 1);
	int ans = 0;
	for (int up = 0; up <= n; up ++) {
		memset(dp, 0, sizeof dp);
		dp[0][0] = 1;
		int cu = 0, fu = 0;
		for (int i = 1; i <= 2 * n; i ++) {
			for (int j = 0; j <= up; j ++) if (dp[i-1][j]) {
				if (f[i].second == 1) {
					add(dp[i][j], 1ll * dp[i-1][j] * max(0, (f[i].first - cu - j)));
				}
				else {
					add(dp[i][j+1], -1ll * dp[i-1][j] * max(0, (f[i].first - cu - j)));
					int cur = -f[i].second;
					add(dp[i][j], 1ll * dp[i-1][j] * max(0, (f[3*n-cur].first - up - n - fu + j)));
				}
			}
			if (f[i].second == 1) cu ++;
			else fu ++;
		}
		add(ans, dp[2*n][up]);
	}
	if (ans < 0) ans += m;
	cout<<ans<<endl;
}
