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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll MOD;
ll add(ll x, ll y) {
	x += y;
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}
ll mult(ll x, ll y) {
	x *= y;
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}

const int N = 505;
ll dp[N][N];
pii a[N];
int bal[N];
int n;

ll solve(int k) {
	for (int i = 0; i <= 2 * n; i++)
		for (int j = 0; j <= k; j++)
			dp[i][j] = 0;
	dp[0][0] = 1;
	for (int i = 0; i < 2 * n; i++)
		for (int j = 0; j <= k; j++) {
			ll w = dp[i][j];
			if (w == 0) continue;
			if (a[i].second == -1) {
				int b = a[i].first - bal[i] - j;
				if (b > 0)
					dp[i + 1][j] = add(dp[i + 1][j], mult(w, b));
			} else {
				int b = a[i].second - (i + (k - j) + bal[2 * n] - bal[i]);
				if (b > 0)
					dp[i + 1][j] = add(dp[i + 1][j], mult(w, b));
				b = a[i].first - bal[i] - j;
				if (j < k && b > 0)
					dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mult(w, b));
			}
		}
	return dp[2 * n][k];
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%lld", &n, &MOD);
	for (int i = 0; i < 2 * n; i++) {
		int x = 0;
		while(i * i + x * x < n * n) x++;
		int y = x;
		while(y < 2 * n && i * i + y * y <= 4 * n * n) y++;
		if (x == 0) {
			a[i] = mp(y, -1);
		} else {
			a[i] = mp(x, y);
		}
	}
	sort(a, a + 2 * n);
//	for (int i = 0; i < 2 * n; i++)
//		eprintf("%d %d\n", a[i].first, a[i].second);
	for (int i = 0; i < 2 * n; i++) {
		bal[i + 1] = bal[i];
		if (a[i].second == -1)
			bal[i + 1]++;
	}
	ll ans = 0;
	for (int k = 0; k <= n; k++) {
		ll w = solve(k);
//		eprintf("%d %lld\n", k, w);
		if (k % 2 == 0)
			ans = add(ans, w);
		else
			ans = sub(ans, w);
	}
	printf("%lld\n", ans);

	return 0;
}
