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;
constexpr int N = 250;
int n, p;
int a[N], b[2 * N], x[2 * N], dp[2][N + 1];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> p;
    for (int i = 0, j = n - 1; i < n; ++i) {
        while (i * i + j * j >= n * n)
            --j;
        a[i] = j + 1;
    }
    for (int i = 0, j = 2 * n - 1; i < 2 * n; ++i) {
        while (i * i + j * j > 4 * n * n)
            --j;
        b[i] = j + 1;
    }
    int ans = 0;
    iota(x, x + 2 * n, 0);
    reverse(x, x + 2 * n);
    stable_sort(x, x + 2 * n, [&](int i, int j) {return (i < n ? a[i] : b[i]) < (j < n ? a[j] : b[j]);});
    for (int k = 0; k <= n; ++k) {
        int cur = 0;
        memset(dp[0], 0, (k + 1) * sizeof(int));
        dp[0][0] = 1;
        int cnt = 0;
        for (int i = 0; i < 2 * n; ++i) {
            if (x[i] < n) {
                cur ^= 1;
                memset(dp[cur], 0, (k + 1) * sizeof(int));
                for (int j = 0; j <= k; ++j) {
                    dp[cur][j] = (dp[cur][j] + 1LL * dp[cur ^ 1][j] * (b[x[i]] - (n + cnt + k - j))) % p;
                    if (j < k)
                        dp[cur][j + 1] = (dp[cur][j + 1] + 1LL * dp[cur ^ 1][j] * (a[x[i]] - (i - cnt + j))) % p;
                }
                ++cnt;
            } else {
                for (int j = 0; j <= k; ++j)
                    dp[cur][j] = 1LL * dp[cur][j] * (b[x[i]] - (i - (cnt - j))) % p;
            }
        }
        ans = (ans + (k % 2 == 0 ? 1 : -1) * dp[cur][k]) % p;
    }
    ans = (ans + p) % p;
    cout << ans << endl;
    return 0;
}