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;
const int N = 555;
int n, mod, f[N], g[N], dp[N][N];
vector<pair<int, int>> a;

int main() {
  scanf("%d%d", &n, &mod);
  for (int i = 0; i < n << 1; i++) {
    for (int j = 0; j < n << 1; j++) if (i * i + j * j < n * n) f[i] = j + 1;
    for (int j = 0; j < n << 1; j++) if (i * i + j * j <= (n << 1) * (n << 1)) g[i] = j + 1;
  }
  for (int i = 0; i < n; i++) {
    a.emplace_back(f[i], i);
  }
  for (int i = n; i < n << 1; i++) {
    a.emplace_back(g[i], i);
  }
  sort(a.begin(), a.end(), [&](pair<int, int> &a, pair<int, int> &b){return a.first == b.first ? a.second > b.second : a.first < b.first;});
  int ans = 0;
  for (int k = 0; k <= n; k++) {
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 0; i < n << 1; i++) {
      for (int j = 0; j <= i; j++) if (dp[i][j]) {
        dp[i + 1][j] = (dp[i + 1][j] + (ll) dp[i][j] * max(0, a[i].first - (i - j))) % mod;
        if (a[i].second < n) {
          dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (ll) dp[i][j] * max(0, g[a[i].second] - (k + n + j))) % mod;
        }
      }
    }
    if (k & 1) {
      ans = (ans + mod - dp[n << 1][n - k]) % mod;
    } else {
      ans = (ans + dp[n << 1][n - k]) % mod;
    }
  }
  printf("%d\n", ans);
}
