#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
namespace fastio {
char rbuf[1 << 23], *p1 = rbuf, *p2 = rbuf, wbuf[1 << 23], *p3 = wbuf;
inline char getc() {
  return p1 == p2 &&
                 (p2 = (p1 = rbuf) + fread(rbuf, 1, 1 << 23, stdin), p1 == p2)
             ? -1
             : *p1++;
}
inline void putc(char x) { (*p3++ = x); }
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T neg = 0;
  while (!isdigit(c)) neg |= !(c ^ '-'), c = getchar();
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (neg) x = (~x) + 1;
}
template <typename T>
void recursive_print(T x) {
  return (!x) ? void() : (recursive_print(x / 10), putc(x % 10 ^ 48), void());
}
template <typename T>
void print(T x) {
  (!x) && (putc('0'), 0);
  (x < 0) && (putc('-'), x = ~x + 1);
  recursive_print(x);
}
template <typename T>
void print(T x, char c) {
  (!x) && (putc('0'), 0);
  (x < 0) && (putc('-'), x = ~x + 1);
  recursive_print(x);
  putc(c);
}
void print_final() { fwrite(wbuf, 1, p3 - wbuf, stdout); }
}  // namespace fastio
const int MAXN = 400;
int mod, fac[MAXN + 5], ifac[MAXN + 5], dp[MAXN + 5], s[MAXN + 5][MAXN + 5],
    f[MAXN + 5];
void init(int n) {
  for (int i = (fac[0] = ifac[0] = ifac[1] + 1); i <= n; i++)
    ifac[i] = 1ll * ifac[mod % i] * (mod - mod / i) % mod;
  for (int i = 1; i <= n; i++)
    fac[i] = 1ll * fac[i - 1] * i % mod,
    ifac[i] = 1ll * ifac[i - 1] * ifac[i] % mod;
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++) f[i] = (f[i] + 1ll * f[j] * fac[i - j]) % mod;
    f[i] = (fac[i] - f[i] + mod) % mod;
  }
  s[0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
      for (int k = 1; k <= i; k++)
        s[i][j] = (s[i][j] + 1ll * s[i - k][j - 1] * fac[k]) % mod;
  dp[2] = (dp[1] = (dp[3] = 0) + 1) + 1;
  for (int i = 4; i <= n; i++) {
    int sum1 = 0, sum2 = 0;
    for (int j = 1; j < i; j++) sum1 = (sum1 + 1ll * f[j] * fac[i - j]) % mod;
    for (int j = 4; j < i; j++) sum2 = (sum2 + 1ll * dp[j] * s[i][j]) % mod;
    int sub = (2ll * sum1 + sum2) % mod;
    dp[i] = (fac[i] - sub + mod) % mod;
  }
}
int main() {
  int qu;
  scanf("%d%d", &qu, &mod);
  init(MAXN);
  while (qu--) {
    int n;
    scanf("%d", &n);
    printf("%d\n", dp[n]);
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

Consider a permutation p_1, p_2, ... p_n of integers from 1 to n. We call a sub-segment p_l, p_{l+1}, ..., p_{r-1}, p_{r} of the permutation an interval if it is a reordering of some set of consecutive integers. For example, the permutation (6,7,1,8,5,3,2,4) has the intervals (6,7), (5,3,2,4), (3,2), and others. 

Each permutation has some trivial intervals — the full permutation itself and every single element. We call a permutation interval-free if it does not have non-trivial intervals. In other words, interval-free permutation does not have intervals of length between 2 and n - 1 inclusive. 

Your task is to count the number of interval-free permutations of length n modulo prime number p. 

Input

In the first line of the input there are two integers t (1 ≤ t ≤ 400) and p (10^8 ≤ p ≤ 10^9) — the number of test cases to solve and the prime modulo. In each of the next t lines there is one integer n (1 ≤ n ≤ 400) — the length of the permutation. 

Output

For each of t test cases print a single integer — the number of interval-free permutations modulo p. 

Examples

Input


4 998244353
1
4
5
9


Output


1
2
6
28146


Input


1 437122297
20


Output


67777575

Note

For n = 1 the only permutation is interval-free. For n = 4 two interval-free permutations are (2,4,1,3) and (3,1,4,2). For n = 5 — (2,4,1,5,3), (2,5,3,1,4), (3,1,5,2,4), (3,5,1,4,2), (4,1,3,5,2), and (4,2,5,1,3). We will not list all 28146 for n = 9, but for example (4,7,9,5,1,8,2,6,3), (2,4,6,1,9,7,3,8,5), (3,6,9,4,1,5,8,2,7), and (8,4,9,1,3,6,2,7,5) are interval-free.

The exact value for n = 20 is 264111424634864638. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
namespace fastio {
char rbuf[1 << 23], *p1 = rbuf, *p2 = rbuf, wbuf[1 << 23], *p3 = wbuf;
inline char getc() {
  return p1 == p2 &&
                 (p2 = (p1 = rbuf) + fread(rbuf, 1, 1 << 23, stdin), p1 == p2)
             ? -1
             : *p1++;
}
inline void putc(char x) { (*p3++ = x); }
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T neg = 0;
  while (!isdigit(c)) neg |= !(c ^ '-'), c = getchar();
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (neg) x = (~x) + 1;
}
template <typename T>
void recursive_print(T x) {
  return (!x) ? void() : (recursive_print(x / 10), putc(x % 10 ^ 48), void());
}
template <typename T>
void print(T x) {
  (!x) && (putc('0'), 0);
  (x < 0) && (putc('-'), x = ~x + 1);
  recursive_print(x);
}
template <typename T>
void print(T x, char c) {
  (!x) && (putc('0'), 0);
  (x < 0) && (putc('-'), x = ~x + 1);
  recursive_print(x);
  putc(c);
}
void print_final() { fwrite(wbuf, 1, p3 - wbuf, stdout); }
}  // namespace fastio
const int MAXN = 400;
int mod, fac[MAXN + 5], ifac[MAXN + 5], dp[MAXN + 5], s[MAXN + 5][MAXN + 5],
    f[MAXN + 5];
void init(int n) {
  for (int i = (fac[0] = ifac[0] = ifac[1] + 1); i <= n; i++)
    ifac[i] = 1ll * ifac[mod % i] * (mod - mod / i) % mod;
  for (int i = 1; i <= n; i++)
    fac[i] = 1ll * fac[i - 1] * i % mod,
    ifac[i] = 1ll * ifac[i - 1] * ifac[i] % mod;
  f[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++) f[i] = (f[i] + 1ll * f[j] * fac[i - j]) % mod;
    f[i] = (fac[i] - f[i] + mod) % mod;
  }
  s[0][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
      for (int k = 1; k <= i; k++)
        s[i][j] = (s[i][j] + 1ll * s[i - k][j - 1] * fac[k]) % mod;
  dp[2] = (dp[1] = (dp[3] = 0) + 1) + 1;
  for (int i = 4; i <= n; i++) {
    int sum1 = 0, sum2 = 0;
    for (int j = 1; j < i; j++) sum1 = (sum1 + 1ll * f[j] * fac[i - j]) % mod;
    for (int j = 4; j < i; j++) sum2 = (sum2 + 1ll * dp[j] * s[i][j]) % mod;
    int sub = (2ll * sum1 + sum2) % mod;
    dp[i] = (fac[i] - sub + mod) % mod;
  }
}
int main() {
  int qu;
  scanf("%d%d", &qu, &mod);
  init(MAXN);
  while (qu--) {
    int n;
    scanf("%d", &n);
    printf("%d\n", dp[n]);
  }
  return 0;
}

```