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. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int N = 1054, SN = 25;
typedef int vec[N], *pvec;
int mod, n, B;
vec a, b, ia, C1, ans;
vec fact, inv, finv;
vec all[SN];
int q, qry[N];
inline int &reduce(int &x) { return x += x >> 31 & mod; }
inline void add(int &x, const int y) { x += y - mod, x += x >> 31 & mod; }
long long PowerMod(long long a, int n, long long c = 1) {
  for (; n; n >>= 1, a = a * a % mod)
    if (n & 1) c = c * a % mod;
  return c;
}
void init(int n) {
  int i;
  for (inv[1] = 1, i = 2; i <= n; ++i)
    inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
  for (*finv = *fact = i = 1; i <= n; ++i)
    fact[i] = (long long)fact[i - 1] * i % mod,
    finv[i] = (long long)finv[i - 1] * inv[i] % mod;
}
void conv(int n, int *a, int *b, int *ret) {
  int i, j;
  if (n < 16) {
    static unsigned long long Ret[33];
    memset(Ret, 0, (n * 2 + 1) << 3);
    for (i = 0; i <= n; ++i)
      for (j = 0; j <= n; ++j) Ret[i + j] += (long long)a[i] * b[j];
    for (i = 0; i <= n * 2; ++i) ret[i] = Ret[i] % mod;
  } else {
    memset(ret, 0, (n * 2 + 1) << 2);
    int h = n / 2 + 1, u[h], v[h], w[2 * h - 1];
    conv(h - 1, a, b, ret);
    conv(n - h, a + h, b + h, ret + h * 2);
    for (i = 0; i < h; ++i) u[i] = a[i], v[i] = -b[i];
    for (i = 0; i <= n - h; ++i) u[i] -= a[i + h], v[i] += b[i + h];
    for (i = 0; i < h; ++i) u[i] += u[i] >> 31 & mod, v[i] += v[i] >> 31 & mod;
    conv(h - 1, u, v, w);
    for (i = 2 * (n - h); i >= 0; --i) add(w[i], ret[i + h * 2]);
    for (i = 2 * (h - 1); i >= 0; --i)
      add(ret[i + h], w[i]), add(ret[i + h], ret[i]);
  }
}
int main() {
  int i, j, k, d;
  long long ret;
  scanf("%d%d", &q, &mod);
  for (i = 0; i < q; ++i) scanf("%d", qry + i);
  n = *std::max_element(qry, qry + q), init(n + 1);
  for (i = 0; i <= n; ++i) a[i] = fact[i + 1];
  for (*ia = i = 1; i <= n; reduce(ia[i++]))
    for (j = 0; j < i; ++j) ia[i] = (ia[i] - (long long)ia[j] * a[i - j]) % mod;
  B = sqrt(n), **all = *b = 1;
  for (j = 1; j <= B; ++j)
    conv(n, all[j - 1], ia, all[j]), memset(all[j] + n, 0, n << 2);
  for (d = 1, j = 0; j < n; j += B) {
    for (k = 1; k <= B && d <= n; ++k, ++d) {
      for (ret = i = 0; i < d; ++i)
        ret = (ret + (long long)all[k][i] * b[d - i - 1]) % mod;
      ans[d] = ret * inv[d] % mod;
    }
    conv(n, b, all[B], C1), memcpy(b, C1, n << 2);
  }
  std::iota(ans, ans + 3, 0);
  for (i = 3; i <= n; ++i) reduce(ans[i] = (i & 1 ? 2 : -2) - ans[i]);
  for (i = 0; i < q; ++i) printf("%d\n", ans[qry[i]]);
  return 0;
}