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;

long long nr, N, mod, dp[1009][1009], fxd[1009];
pair < long long, long long > v[1009];

//long long add (long long x, long long y) {long long ans = x + y; if (ans >= mod) ans -= mod; return ans;}
long long subtract (long long x, long long y) {return ((x - y) % mod + mod) % mod;}
long long mul (long long x, long long y) {return ((1LL * x % mod * y % mod) + mod) % mod;}
void adto (long long &x, long long y) {x = (x + y) % mod;}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%lld %lld", &N, &mod);
if (N == 1)
{
    printf ("1\n");
    return 0;
}
int l = N * N, r = 4 * N * N;
for (int i=2 * N - 1; i>=0; i--)
{
    int x = -1, y = -1;
    for (int j=0; j<2 * N; j++)
        if (i * i + j * j >= l && i * i + j * j <= r)
        {
            if (x == -1) x = j;
            y = j;
        }
    if (x > 0)
    {
        v[++nr] = {x - 1, y}; ///x <= N < y
        assert (x - 1 < N && N <= y);
    }
    else fxd[y] ++;
}
v[nr + 1] = {N - 1, 2 * N - 1};
long long ans = 0;
for (int K=0; K<=2 * N; K ++)
{
    dp[0][0] = 1;
    int prvX = -1, prvY = N - 1, leftSoFar = 0, rightSoFar = 0;
    for (int i=1; i<=nr + 1; i++)
    {
        for (int j=leftSoFar; j<=K; j++)
            if (dp[i - 1][j] > 0)
            {
                ///adding pair (v[i].first, v[i].second)
                ///firstly, [prvX+1..v[i].first]x[prvY+1..v[i].second] to be added
                int coef = 1, bef = j, extra = 0;
                for (int k=prvX + 1; k<=v[i].first; k++)
                {
                    int steps = fxd[k];
                    extra += fxd[k];
                    while (steps --)
                    {
                        if (k + 1 - bef < 0) coef = 0;
                        coef = mul (coef, k + 1 - bef),
                        bef ++;
                    }
                }
                int oldBef = bef;
                bef = K + rightSoFar + ((i - 1) - (j - leftSoFar));
                for (int k=prvY + 1; k<=v[i].second; k++)
                {
                    int steps = fxd[k];
                    while (steps --)
                    {
                        if (k + 1 - bef < 0) coef = 0;
                        coef = mul (coef, k + 1 - bef),
                        bef ++;
                    }
                }
                if (i == nr + 1)
                    adto (dp[i][j + extra], mul (dp[i - 1][j], coef));///there's no actual new pair
                else
                {
                    int curr = mul (dp[i - 1][j], coef);
                    if (v[i].second + 1 >= bef)
                        adto (dp[i][j + extra], mul (curr, v[i].second + 1 - bef));
                    //curr = mul (curr, mod - 1);///it's negative now because of wrong inequality
                    if (curr > 0) curr = mod - curr;
                    if (v[i].first + 1 >= oldBef)
                        adto (dp[i][j + extra + 1], mul (curr, v[i].first + 1 - oldBef));
                }
            }
        for (int j=prvX + 1; j<=v[i].first; j++)
            leftSoFar += fxd[j];
        prvX = v[i].first;
        for (int j=prvY + 1; j<=v[i].second; j++)
            rightSoFar += fxd[j];
        prvY = v[i].second;
    }
/*    if (K == 1)
    {
        for (int i=1; i<=nr; i++)
        {
            printf ("after adding [%d, %d]: ", v[i].first, v[i].second);
            for (int j=0; j<2 * N; j++)
                printf ("%2d ", dp[i][j]);
            printf ("\n");
        }
    }
    printf ("K=%d -> +%d\n", K, dp[nr + 1][K]);*/
    adto (ans, dp[nr + 1][K]);
    for (int i=0; i<=nr + 1; i++)
        for (int j=0; j<=2 * N; j++)
            dp[i][j] = 0;
}
printf ("%lld\n", ans);
return 0;
}
