#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL
vector<int> get(vector<int> p){
	vector<int> res(p.size());
	rep(i,p.size()){
		res[p[i]] = i;
	}
	return res;
}
vector<int> op(vector<int> p,vector<int> q){
	vector<int> res(p.size());
	rep(i,p.size()){
		res[i] = p[q[i]];
	}
	return res;
}

mint f0[5000006],f1[5000006],f2[5000006],f3[5000006],f4[5000006],f5[5000006];
void p(mint n){
	printf("%d\n",n.val());
}
mint gu(int n){
	vector<int> p(n);
	rep(i,n)p[i] = i;
	mint res = 0;
	do{
		set<vector<int>> s;
		s.insert(p);
		
		rep(_,2){
			auto x = p;
			rep(i,10){
				if(i%2==_){
					reverse(x.begin(),x.end());
				}
				else x = get(x);
				s.insert(x);
			}
		}
		
		res += s.size();
	}
	while(next_permutation(p.begin(),p.end()));
	return res;
	
}
int main(){

	/*
	int n;
	cin>>n;
	vector<int> p(n);
	rep(i,n)p[i] = i;
	vector<int> c(1<<5);
	vector<int> rev(n);
	rep(i,n)rev[i] = n-i-1;
	do{
		int cur = 0;
		if(p==get(p))cur++;
		if(p==op(rev,get(p)))cur+=2;
		if(p==op(get(p),rev))cur+=4;
		if(p==op(rev,op(p,rev)))cur+=8;
		if(p==op(rev,op(get(p),rev)))cur+=16;
		c[cur]++;
	}
	while(next_permutation(p.begin(),p.end()));

	rep(i,1<<5){
		if(c[i]==0)continue;
		cout<<bitset<5>(i)<<' '<<c[i]<<endl;
	}

*/
	int _t,M;
	cin>>_t>>M;
	mint::set_mod(M);
	
	f1[0] = 1;
	f4[0] = 1;
	for(int i=1;i<=5000000;i++){
		f1[i] = f1[i-1];
		if(i>=2){
			f1[i] += f1[i-2] * (i-1);
		}
		f4[i] = f1[i];
	}
	f5[0] = 1;
	f5[1] = 1;
	for(int i=2;i<=5000000;i++){
		f5[i] = f5[i-2];
		if(i>=4)f5[i] += f5[i-4] * ((i-2)/2);
		f5[i] *= 2;
	}
	f2[0] = 1;
	f2[1] = 1;
	for(int i=2;i<=5000000;i++){
		f2[i] = f2[i-2] * (i/2) * 2;
	}
	

	f3[0] = 1;
	f3[1] = 1;
	for(int i=2;i<=5000000;i++){
		if(i-4>=0){
			f3[i] = f3[i-4] * ((i-2)/2) * 2;
		}
	}
	
	f0[0] = 1;
	rep(i,5000000){
		f0[i+1] = f0[i] * (i+1);
	}
	rep(i,5000001){
		f4[i] -= f5[i];
		f2[i] -= f5[i];
		f1[i] -= f5[i];
		f2[i] -= f3[i];
		f0[i] -= f1[i] + f2[i] + f3[i] + f4[i] + f5[i];
	}/*
	cout<<f0[n].val()<<endl;
	cout<<f1[n].val()<<endl;
	cout<<f2[n].val()<<endl;	
	cout<<f3[n].val()<<endl;
	cout<<f4[n].val()<<endl;
	cout<<f5[n].val()<<endl;
**/
	rep(_,_t){
		int n;
		scanf("%d",&n);
		if(n==1){
			p(1);
			continue;
		}
		p(f0[n] * 8 + f1[n] * 4 + f2[n] * 4 + f3[n] * 2 + f4[n] * 4+ f5[n] * 2);
		//p(f4[n]);
		//p(gu(n));
	//	p(fn[n]);
//		p(f3[n]);
	}
		
	return 0;
}