#include<bits/stdc++.h>
using ll = long long;
constexpr int maxn = 3e7 + 10, N = 3e7, M = 1e7;
ll mod;
inline ll qpow(ll a, ll b, ll v = 1) {
   while (b) {
      if (b & 1) (v *= a) %= mod;
      (a *= a) %= mod, b >>= 1;
   }
   return v;
}
ll fac[maxn], ifac[maxn], inv[maxn];
inline ll binom(int n, int m) {
   return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll f[maxn], g[maxn];
int main() {
   int q;
   scanf("%d%lld", &q, &mod);
   for (int i = fac[0] = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
   ifac[N] = qpow(fac[N], mod - 2);
   for (int i = N; i; i--) ifac[i - 1] = ifac[i] * i % mod;
   for (int i = inv[0] = 1; i <= N; i++) inv[i] = ifac[i] * fac[i - 1] % mod;
   const ll inv2 = inv[2], inv6 = inv[6];
   ll pw = 1ll;
   for (int i = 0; i <= M; i++) {
      f[i] = fac[3 * i] * ifac[i] % mod * pw % mod;
      (pw *= inv6) %= mod;
   }
   g[0] = g[1] = 1, g[2] = inv[2];
   for (int i = 3; i <= N; i++) {
      g[i] = (g[i - 1] + g[i - 3] * inv2 % mod) * inv[i] % mod;
   }
   for (int n; q--; ) {
      scanf("%d", &n);
      if (n % 3 == 0) {
         printf("%lld\n", f[n / 3] % mod);
         continue;
      }
      ll ans = g[n - 1] * fac[n] % mod;
      if (n % 3 == 2) {
         (ans += mod - binom(n, 2) * f[n / 3] % mod) %= mod;
      }
      printf("%lld\n", ans);
   }
   return 0;
}