#include using namespace std; using ll = long long; const int iinf = 1e9; const ll inf = 1e18; template struct Mint { using M=Mint; ll v; M& put(ll x) { v=(x>=1; } return res; } M inv() { return pow(mod-2); } }; template ostream&operator<<(ostream&o,Mintv){return o< ostream& operator<<(ostream &o, vector v) { for (int i = 0; i < v.size(); i++) o << v[i] << (i+1 struct SegTree { using F = function; int n; F f; T ti; vector dat; SegTree() {} SegTree(F f, T ti,int num) : f(f), ti(ti) { n = max(__bit_ceil(num), 1); dat.assign(n << 1, ti); } SegTree(F f,T ti,vector&v):SegTree(f,ti,v.size()){ for (int i = 0; i < v.size(); i++) dat[n + i] = v[i]; for(int i=n-1;i;i--) dat[i]=f(dat[i*2], dat[i*2+1]); } void set_val(int k, T x) { dat[k += n] = x; while(k >>= 1) dat[k] = f(dat[k*2], dat[k*2+1]); } T query(int a, int b) { if (a >= b) return ti; T vl = ti, vr = ti; for (int l=a+n, r=b+n; l>=1, r>>=1) { if (l & 1) vl = f(vl, dat[l++]); if (r & 1) vr = f(dat[--r], vr); } return f(vl, vr); } }; const int MOD = 998244353; using mint = Mint; vector involution_counts(int N, ll mod) { vector a(N+1); if (N >= 0) a[0] = 1; if (N >= 1) a[1] = 1; for (int i = 2; i <= N; ++i) { a[i] = (a[i-1] + ll(i-1) * a[i-2]) % mod; } return a; } // 2) inv(P)==P かつ rev(P)==inv(rev(P)) となる順列数 vector inv_and_rev_involution_counts(int N, ll mod) { vector a(N+1); a[0] = 1; a[1] = 1; a[2] = 2; for (int i = 3; i <= N; ++i) { if (i & 1) { a[i] = a[i-1]; } else { a[i] = (a[i-2]*2+a[i-4]*ll(i-2))%mod; } } return a; } // 3) rev(inv(P)) == inv(rev(P)) == P となる順列数 vector rev_inv_eq_inv_rev_eq_P_counts(int N, ll mod) { vector a(N+1); int M = N/2; // m! を前計算 vector v(M+1, 1); for (int i = 1; i <= M; ++i) v[i] = i; SegTree seg([&](ll x, ll y) { return (x*y)%mod; }, 1, v); for (int n = 0; n <= N; ++n) { int m = n / 2; // m が偶数なら m!/(m/2)!, そうでなければ 0 if (m % 2 == 0) { a[n] = seg.query(m/2+1, m+1); // a[n] = fact[m] / fact[m/2]; } else { a[n] = 0; } } return a; } // 4) rev(inv(P)) == inv(rev(P)) となる順列数(R と可換) vector commute_counts(int N, ll mod) { vector a(N+1); int M = N / 2; vector fact(M+1, 1); vector pow2(M+1, 1); for (int i = 1; i <= M; ++i) { fact[i] = fact[i-1] * i % mod; pow2[i] = pow2[i-1] * 2 % mod; } for (int n = 0; n <= N; ++n) { int m = n / 2; a[n] = fact[m] * pow2[m] % mod; } return a; } int main() { cin.tie(0)->sync_with_stdio(false); int n; ll m; cin >> n >> m; // int N = 500; int N = 5000001; vector fact(N+1, 1); for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % m; auto a = involution_counts(N,m); auto b = inv_and_rev_involution_counts(N,m); auto c = rev_inv_eq_inv_rev_eq_P_counts(N,m); auto d = commute_counts(N,m); // cout << a<< endl; // cout << b<< endl; // cout << c<< endl; // cout < ans(N+1); for (int i = 0; i <= N; ++i) { ans[i] = fact[i]*8-a[i]*8+b[i]*6-c[i]*2-d[i]*4; ans[i] %= m; if (ans[i] < 0) ans[i] += m; } ans[1] = 1; // cout << fact << endl; // cout << ans << endl; for (int i = 0; i < n; i++) { int t; cin >> t; cout << ans[t] << endl; } }