#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
const int N=3e7+3;
int n,T,mo,jc[N],jinv[N],iv[N],f[N],g[N];
ll ksm(ll x,int y){ll s=1;for(;y;y>>=1,x=x*x%mo)if(y&1)s=s*x%mo;return s;}
int main()
{
	scanf("%d%d",&T,&mo);
	n=3e7;
	jc[0]=1;fo(i,1,n) jc[i]=1ll*jc[i-1]*i%mo;
	jinv[n]=ksm(jc[n],mo-2);fd(i,n,1) jinv[i-1]=1ll*jinv[i]*i%mo;
	fo(i,1,n) iv[i]=1ll*jinv[i]*jc[i-1]%mo;
	f[0]=f[1]=1;f[2]=iv[2];
	fo(i,3,n) f[i]=1ll*(f[i-1]+((f[i-3]&1)?(mo+f[i-3]>>1):(f[i-3]>>1)))*iv[i]%mo;
	g[0]=1;
	for(int j=3;j<=n;j+=3) g[j]=1ll*g[j-3]*iv[6]%mo;
	for(int i=1,j=3;j<=n;++i,j+=3) g[j]=1ll*g[j]*jinv[i]%mo;
	while(T--)
	{
		scanf("%d",&n);
		if(n==1){printf("1\n");continue;}
		if(n%3==0) printf("%lld\n",1ll*g[n]*jc[n]%mo);
		else printf("%lld\n",(f[n-1]+g[n]+1ll*g[n-2]*(mo-iv[2]))%mo*jc[n]%mo);
	}
}