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;

int N , M , dp[503][253] , arr[503];

int main(){
	cin >> N >> M;
	for(int i = 0 ; i < 2 * N ; ++i)
		if(i < N) arr[i] = sqrt(N * N - i * i - 1);
		else arr[i] = -sqrt(4 * N * N - i * i);
	sort(arr , arr + 2 * N , [](int p , int q){return abs(p) < abs(q);});
	int sum = 0;
	for(int i = 0 ; i <= N ; ++i){
		memset(dp , 0 , sizeof(dp)); dp[0][i] = 1; int cnt = N , cnt1 = 0;
		for(int j = 0 ; j < 2 * N ; ++j)
			if(arr[j] < 0){
				for(int k = 0 ; k <= i ; ++k)
					dp[j + 1][k] = 1ll * dp[j][k] * (-arr[j] - (i - k + cnt1) + 1) % M;
				++cnt1;
			}
			else{
				--cnt;
				for(int k = 0 ; k <= i ; ++k){
					dp[j + 1][k] = 1ll * dp[j][k] * (min(2 * N - 1 , (int)sqrt(4 * N * N - cnt * cnt)) - (N + (N - cnt - 1) + k) + 1) % M;
					if(k) dp[j + 1][k - 1] = (dp[j + 1][k - 1] + 1ll * dp[j][k] * (arr[j] - (cnt1 + i - k) + 1)) % M;
				}
			}
		sum = (sum + (i & 1 ? M - 1ll : 1ll) * dp[2 * N][0]) % M;
	}
	cout << sum; return 0;
}