#include<bits/stdc++.h>
#define ll long long
using namespace std;int g[20][1000005],tot;pair<int,int>s[20];
void exgcd(int x,int y,int &a,int &b){if(!y)return a=1,b=0,void();exgcd(y,x%y,b,a),b-=x/y*a;}
int inv(int X,int M){int x,y;exgcd(X,M,x,y);return (x+M)%M;}
void init(int p,int M,int *f){f[0]=1;for(int i=1;i<=M;i++)f[i]=1ll*f[i-1]*(i%p?i:1)%M;}
int qp(int x,ll y,int M){int ans=1;while(y)ans=1ll*ans*(y&1?x:1)%M,x=1ll*x*x%M,y>>=1;return ans;}
int F(ll x,int p,int M,int *f){if(!x)return 1;return 1ll*F(x/p,p,M,f)*(x/M&1?M-1:1)%M*f[x%M]%M;}
ll G(ll x,int p){return x<p?0:G(x/p,p)+x/p;}
int c(ll x,int p,int M,int *f){int f1=F(2*x,p,M,f),f2=inv(F(x,p,M,f),M);
	return 1ll*f1*qp(p,G(2*x,p)-2*G(x,p),M)%M*f2%M*f2%M;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int tid,T,Mod,mod;cin>>tid>>T>>Mod,mod=Mod;
	for(int j,i=2;i*i<=mod;i++)if(mod%i==0){
		j=1;while(mod%i==0)j*=i,mod/=i;s[++tot]={i,j},init(i,j,g[tot]);
	}if(mod>1)s[++tot]={mod,mod},init(mod,mod,g[tot]);
	while(T--){ll n;cin>>n;int asw=0;
		for(int id=1;id<=tot;id++){int i=s[id].first,j=s[id].second,k=Mod/j;
			asw=(asw+1ll*k*inv(k,j)%Mod*c(n,i,j,g[id]))%mod;
		}
		cout<<n%mod*qp(Mod+1>>1,2*n,Mod)%mod*asw%mod<<"\n";
	}
}
/*
0 5 9
1
2
3
4
5
*/

/usr/bin/ld: /tmp/cc0xHwDi.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2eeFvk.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc2eeFvk.o: in function `main':
implementer.cpp:(.text.startup+0x2f): undefined reference to `init(int, int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x174): undefined reference to `ask(long long)'
collect2: error: ld returned 1 exit status