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;

typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pi;

#define fi first
#define se second

int read() {
  int res = 0, w = 1; char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), w = -1;
  while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();
  return res * w;
}

const int N= 510;

int n, m, dp[N][N];
pi val[N];

void add(int &a, int b) {
  if ((a += b) >= m) a -= m;
}

void sub(int &a, int b) {
  if ((a -= b) < 0) a += m;
}

int mul(int a, int b) {
  return 1ll * a * b % m;
}

int main() {
#ifdef dream_maker
//  freopen("tst.in", "r", stdin);
#else
  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);
#endif
  n = read(), m = read();
  int a = 2 * n - 1, b = 2 * n - 1;
  for (int i = 0; i < 2 * n; i++) {
    while (i * i + a * a >= n * n && a >= 0) a--;
    while (i * i + b * b > 4 * n * n && b >= 0) b--;
    if (a < 0) val[i + 1] = pi(b + 1, 0);
    else val[i + 1] = pi(a + 1, b + 1);
  }
  sort(val + 1, val + 2 * n + 1);
//  for (int i = 1; i <= 2 * n; i++) cout << val[i].first << " : " << val[i].second << endl;
  int ans = 0;
  for (int k = 0; k <= n; k++) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int f = 0, g = 0;
    for (int i = 1; i <= 2 * n; i++) {
      for (int j = 0; j <= k; j++) {
        if (val[i].second) {
          if (j) add(dp[i][j], mul(dp[i - 1][j - 1], val[i].first - j - g + 1));
          add(dp[i][j], mul(dp[i - 1][j], val[i].second - k - n - (f - j)));
        } else {
          add(dp[i][j], mul(dp[i - 1][j], val[i].first - j - g));
        }
      }
      f += val[i].second != 0;
      g += val[i].second == 0;
    }
//    cout << k << " " << dp[2 * n][k] << endl;
    if (k & 1) sub(ans, dp[2 * n][k]);
    else add(ans, dp[2 * n][k]); 
  }
  cout << ans << endl;
  return 0;
}
