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 read();
int n, m;
void Add(int &x, int y) { (x += y) >= m ? x -= m : y; }
struct P {
    int l, r;
} p[1003];
bool cmp(P a, P b) { return a.l == b.l ? a.r < b.r : a.l < b.l; }
bool check(int x, int y) {
    int t = x * x + y * y;
    return t >= n * n && t <= 4 * n * n;
}

int f[1003][1003];
int solve(int sum) {
    int c1 = 0, c2 = 0;
    f[0][0] = 1;
    for (int i = 1; i <= (n << 1); ++i) {
        if (!p[i].r) {
            ++c1;
            for (int j = 0; j <= min(sum, c2); ++j) {
                int x = p[i].l + 1 - (c1 + j - 1);
                f[i][j] = 1ll * f[i - 1][j] * x % m;
            }
        } else {
            f[i - 1][++c2] = 0;
            for (int j = 0; j <= min(sum, c2); ++j) {
                int x = p[i].r + 1 - (n + sum + (c2 - 1 - j));
                f[i][j] = 1ll * f[i - 1][j] * x % m;
                if (j > 0) {
                    x = p[i].l + 1 - (c1 + j - 1);
                    Add(f[i][j], 1ll * f[i - 1][j - 1] * x % m);
                }
            }
        }
    }
    return f[n << 1][sum];
}

int main() {
    n = read(), m = read();
    int L = n, R = 2 * n - 1;
    for (int i = 0; i < n; ++i) {
        while (check(L - 1, i)) L--;
        while (!check(R, i)) R--;
        p[i + 1] = (P){L - 1, R};
    }
    for (int i = n; i < (n << 1); ++i) {
        while (!check(R, i)) R--;
        p[i + 1] = (P){R, 0};
    }

    sort(p + 1, p + 1 + (n << 1), cmp);
    int res = 0;
    for (int i = 0, t = 1; i <= n; ++i)
        Add(res, 1ll * t * solve(i) % m), t = m - t;
    printf("%d\n", res);
    return 0;
}
const int _SIZE = 1 << 22;
char ibuf[_SIZE], *iS = ibuf, *iT = ibuf;
#define gc                                                         \
    (iS == iT ? iT = ((iS = ibuf) + fread(ibuf, 1, _SIZE, stdin)), \
     (iS == iT ? EOF : *iS++) : *iS++)
int read() {
    int x = 0, f = 1;
    char c = gc;
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = gc;
    while (isdigit(c)) x = x * 10 + c - '0', c = gc;
    return x * f;
}