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;

namespace TYC
{
	typedef long long ll;
	typedef pair<int, int> pii;
	const int N = 505;

	int n, tot, mod, F[N][N];
	pii A[N];

	int solve(const int k)
	{
		memset(F, 0, sizeof(F));
		F[0][0] = 1;
		int c1 = 0, c2 = 0;
		for (int i = 0; i < tot; i++)
			if (A[i].second == 0)
			{
				for (int j = 0; j <= c2; j++)
					F[i + 1][j] = int((ll)F[i][j] * (A[i].first + 1 - c1 - j) % mod);
				c1++;
			}
			else
			{
				for (int j = 0; j <= c2; j++)
				{
					F[i + 1][j + 1] = int((F[i + 1][j + 1] + (ll)F[i][j] * (A[i].first + 1 - c1 - j) % mod) % mod);
					F[i + 1][j] = int((F[i + 1][j] + (ll)F[i][j] * (A[i].second + 1 - n - k - (c2 - j)) % mod) % mod);
				}
				c2++;
			}
		return F[tot][k];
	}

	void work()
	{
		scanf("%d%d", &n, &mod);
		tot = n << 1;
		for (int i = 0; i < n; i++)
		{
			int l = int(ceil(sqrt((double)n * n - (double)i  * i)));
			int r = int(floor(sqrt((double)n * n * 4 - (double)i * i)));
			A[i] = {l - 1, min(tot - 1, r)};
		}
		for (int i = n; i < tot; i++)
			A[i] = {int(floor(sqrt((double)n * n * 4 - (double)i * i))), 0};

		sort(A, A + tot);
		int ans = 0;
		for (int i = 0, d = 1; i <= n; i++, d = -d)
			ans = int(((ll)ans + d * solve(i) + mod) % mod);
		printf("%d\n", ans);
	}
}

int main()
{
	TYC::work();
	return 0;
}