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;

const int MAX_N = 504;

typedef long long ll;

ll MOD;
int N, U[MAX_N], L[MAX_N], ord[MAX_N];

int sq(int x) { return x * x; }

void init() {
    scanf("%d%lld", &N, &MOD);
    for (int i = 0; i < 2 * N; i++) {
        U[i] = 0;
        L[i] = 2 * N - 1;
        for (int j = 0; j < 2 * N; j++) {
            if (sq(i) + sq(j) >= sq(N) && sq(i) + sq(j) <= sq(2 * N)) {
                U[i] = max(U[i], j);
                L[i] = min(L[i], j);
            }
        }
    }
    pair<int, int> _ord[MAX_N];
    for (int i = 0; i < N; i++) {
        _ord[i] = make_pair(L[i] - 1, i);
    }
    for (int i = N; i < 2 * N; i++) {
        _ord[i] = make_pair(U[i], i);
    }
    sort(_ord, _ord + 2 * N, [](pair<int, int> a, pair<int, int> b) {
                                 if (a.first != b.first) return a.first < b.first;
                                 return a.second > b.second;
                             });
    for (int i = 0; i < 2 * N; i++) ord[i] = _ord[i].second;
}

ll F[MAX_N][MAX_N], ans;
void solve() {
    for (int m = 0; m <= N; m++) {
        memset(F, 0, sizeof(F));
        F[0][0] = 1;
        int fixed = 0;
        for (int i = 0; i < 2 * N; i++) {
            int x = ord[i];
            if (x < N) {
                for (int j = 0; j <= m; j++) {
                    (F[i + 1][j + 1] += F[i][j] * max(L[x] - fixed - j, 0)) %= MOD;
                    (F[i + 1][j] += F[i][j] * max(U[x] + 1 - i - (m - j) - (N - fixed), 0)) %= MOD;
                }
            } else {
                for (int j = 0; j <= m; j++) {
                    (F[i + 1][j] += F[i][j] * max(U[x] + 1 - fixed - j, 0)) %= MOD;
                }
                fixed++;
            }
        }
        (ans += (m & 1 ? MOD - 1 : 1) * F[2 * N][m]) %= MOD;
    }
    printf("%lld\n", ans);
}

int main() {
    init();
    solve();
}
