#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    ll M;
    cin >> T >> M;
    vector<int> Ns(T);
    int maxN = 0;
    for(int i = 0; i < T; i++){
        cin >> Ns[i];
        maxN = max(maxN, Ns[i]);
    }

    // 1) factorial
    vector<ll> fact(maxN+1, 0);
    fact[0] = 1;
    for(int i = 1; i <= maxN; i++){
        fact[i] = fact[i-1] * i % M;
    }

    // 2) involution numbers a[n]
    vector<ll> a(maxN+1, 0);
    a[0] = 1; 
    if(maxN >= 1) a[1] = 1;
    for(int n = 2; n <= maxN; n++){
        a[n] = (a[n-1] + (ll)(n-1) * a[n-2]) % M;
    }

    // 3) central-symmetric count c[n] = (floor(n/2))! * 2^{floor(n/2)} mod M
    vector<ll> c(maxN+1, 0), pow2(maxN+1, 0);
    pow2[0] = 1;
    for(int i = 1; i <= maxN; i++){
        pow2[i] = (pow2[i-1] * 2) % M;
    }
    // we also need factorial up to floor(maxN/2)
    int half = maxN/2;
    vector<ll> fact_half(half+1,0);
    fact_half[0] = 1;
    for(int i = 1; i <= half; i++){
        fact_half[i] = fact_half[i-1] * i % M;
    }
    for(int n = 0; n <= maxN; n++){
        int m = n/2;
        c[n] = fact_half[m] * pow2[m] % M;
    }

    // 4) intersection count d[n] = 2^{floor(n/2)} mod M
    vector<ll> d(maxN+1, 0);
    for(int n = 0; n <= maxN; n++){
        d[n] = pow2[n/2];
    }

    // 5) まとめて S[n] を計算
    //    S[0]=1, S[1]=1, S[2]=4 (検算済み)
    vector<ll> S(maxN+1, 0);
    if(maxN >= 0) S[0] = 1 % M;
    if(maxN >= 1) S[1] = 1 % M;
    if(maxN >= 2) S[2] = 4 % M;
    for(int n = 3; n <= maxN; n++){
        ll v = (8LL * fact[n]) % M;
        v = (v - 4LL * a[n] % M + M) % M;
        v = (v - 8LL * c[n] % M + M) % M;
        v = (v + 2LL * d[n] % M) % M;
        S[n] = v;
    }

    // 出力
    for(int n : Ns){
        cout << S[n] << "\n";
    }
    return 0;
}