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>
#define rep(i, x, y) for (long long i = x; i <= y; i++)
#define fi first
#define se second
using namespace std;

const int N = 505;
typedef long long ll;
typedef pair<ll, ll> pll;
ll n, mod, dp[N][N];
pll a[N];

ll calc(ll x, ll y) {
    ll ret = 0;
    while (ret < 2 * n - 1 && (ret + 1) * (ret + 1) + x <= y)
        ++ret;
    return ret;
}

void add(ll &x, ll y) {
    x = (x + y) % mod;
}

ll solve(ll k) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int A = 0, C = 0;
    rep(i, 0, 2 * n - 1) {
        if (~a[i].se) {
            rep(j, 0, A) {
                add(dp[i + 1][j + 1], dp[i][j] * (a[i].fi - j - C) % mod);
            }
            rep(j, 0, A) {
                add(dp[i + 1][j], dp[i][j] * (a[i].se - k - n - (A - j)) % mod);
            }
            ++A;  // 这里的 A 其实最终是 A 和 B 的总个数
        } else {
            rep(j, 0, A) {
                add(dp[i + 1][j], dp[i][j] * (a[i].fi - j - C) % mod);
            }
            ++C;
        }
    }
    return dp[n * 2][k];
}

int main() {
    cin >> n >> mod;
    rep(i, 0, n - 1) {
        a[i] = make_pair(calc(i * i, n * n - 1) + 1, calc(i * i, 4 * n * n) + 1);  // 一个范围
    }
    rep(i, n, 2 * n - 1) {
        a[i] = make_pair(calc(i * i, 4 * n * n) + 1, -1);
    }
    sort(a, a + 2 * n);
    ll ans = 0;
    rep(i, 0, n) {
        (ans += 1ll * (i & 1 ? mod - 1 : 1) * solve(i) % mod) %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}