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 pii pair<int, int>
#define mp make_pair

const int maxN = 505;

int n, mod, ans, m;
int f[maxN + 1][maxN + 1];

pii a[maxN + 1];

inline int ADD(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }

inline int SUB(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }

int main()
{
	scanf("%d %d", &n, &mod);
	
	int p = 2 * n - 1, q = 2 * n - 1;
	for(int i = 0; i < 2 * n; i++)
	{
		while(i * i + p * p > (2 * n) * (2 * n) && p >= 0) p --;
		while(i * i + q * q >= n * n && q >= 0) q --;
		if(q < 0) a[++ m] = mp(p + 1, 0);
		else a[++ m] = mp(q + 1, p + 1);
	}

	sort(a + 1, a + m + 1);

	for(int k = 0; k <= n; k++)
	{
		memset(f, 0, sizeof(f));
		f[0][0] = 1;
		int s0 = 0, s1 = 0;
		for(int i = 1; i <= m; i++)
		{
			for(int j = 0; j <= k; j++)
			{
				int res = f[i - 1][j];
				if(!a[i].second) f[i][j] = ADD(f[i][j], 1ll * res * (a[i].first - s0 - j) % mod);
				else
				{
					if(j < k) f[i][j + 1] = ADD(f[i][j + 1], 1ll * res * (a[i].first - s0 - j) % mod);
					f[i][j] = ADD(f[i][j], 1ll * res * (a[i].second - k - n - (s1 - j)) % mod);
				}
			}
			if(!a[i].second) s0 ++;
			else s1 ++;
		}
		ans = (k & 1) ? SUB(ans, f[m][k]) : ADD(ans, f[m][k]);
	}

	printf("%d\n", ans);
	return 0;
}
