//Linkwish's code
//Ciallo～(∠・ω< )⌒★
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define si static inline
#define fi first
#define se second
using namespace std;typedef long long ll;typedef __int128 li;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;typedef const int ci;
typedef const ll cl;const int iinf=INT_MAX;const ll linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

bool ST;
namespace LinkWish{

	char buf[1<<21],*bp1,*bp2;
	si void init(){if(bp1==bp2)bp2=(bp1=buf)+fread(buf,1,1<<20,stdin);}
	si char Texas(){return (init(),bp1!=bp2)?*bp1++:EOF;}
	si void read(int &x){
		char ch=Texas();
		for(;ch<'0'||ch>'9';ch=Texas());
		for(x=0;ch>='0'&&ch<='9';ch=Texas())x=x*10+(ch^48);
	}

	int Stk[20],tp;
	si void write(ll x){
		if(!x)return putchar('0'),void();
		while(x)Stk[++tp]=x%10,x/=10;
		while(tp)putchar('0'+Stk[tp--]);
	}

	int TestCase,mod;

	const int N=1000005,M=20;

	si int qpow(int x,int y,int p){
		int res=1;
		for(;y;x=1ll*x*x%p,y>>=1)if(y&1)res=1ll*res*x%p;
		return res;
	}
	si void exgcd(int a,int b,int &x,int &y){
		if(!b)return x=1,y=0,void();
		exgcd(b,a%b,x,y);int tmp=x;x=y;y=tmp-(a/b)*y;
	}

	int cnt;

	int stk[100],top;
	struct Texas{
		int p,pk;
		int mul[N],pw[N];
		int f[N];
		int G(int n){if(n<p)return 0;return n/p+G(n/p);}
		int F(int n){
			cnt++;
			if(!n)return 1;
			if(n<N&&~f[n])return f[n];
			int res=mul[n%pk];
			if((n/pk)&1)res=res*(pk-1)%pk;
			if(!res)return 0;
			return F(n/pk)*res%pk;
		}
		inline void init(){
			mul[0]=1,pw[0]=1;
			for(int i=1;i<=pk;i++){
				mul[i]=mul[i-1],pw[i]=1ll*pw[i-1]*p%pk;
				if(i%p)mul[i]=mul[i]*i%pk;
			}
			memset(f,-1,sizeof f);
			for(int i=1;i<N;i++)f[i]=F(i);
		}		
		inline int inv(int n){int x,y;exgcd(n,pk,x,y);return (x+pk)%pk;}
		inline int calc(int n,int m){
			int k=G(n)-G(m)-G(n-m);
			if(k>pk)return 0;
			return F(n)*inv(F(m))%pk*inv(F(n-m))%pk*pw[k]%pk;
			// return F(n)*inv(F(m))%pk*inv(F(n-m))%pk*qpow(p,G(n)-G(m)-G(n-m),pk)%pk;
		}
	}G[M];

	int tot;
	si int C(int n,int m){
		int sum=0;
		for(int i=0;i<tot;i++){
			int nm=mod/G[i].pk;
			(sum+=G[i].inv(nm)*nm%mod*G[i].calc(n,m)%mod)%=mod;
		}
		return sum;
	}

	int inv2,inv4;

	void init (int o, int p){
		TestCase=o,mod=p;
		inv2=(mod+1)/2,inv4=inv2*inv2%mod;

		int x=p;
		for(int i=2;i*i<=p;i++){
			if(x%i==0){
				G[tot].p=i,G[tot].pk=1;
				while(x%i==0)G[tot].pk*=i,x/=i;
				G[tot].init();
				tot++;
			}
		}
		if(x>1)G[tot].p=G[tot].pk=x,G[tot].init(),tot++;
	}
	int ask (long long n){
		return qpow(inv4,n,mod)*(n%mod)%mod*C(2*n,n)%mod;
	}
	si void mian(){
		int o, T, p;
		read(o),read(T),read(p);
		init(o, p);
		// int st=0;
		for (int i = 1; i <= T; i++){
			// if(i%100000==0)cerr<<i<<' '<<1.0*(clock()-st)/CLOCKS_PER_SEC<<endl,st=clock();
			long long n;
			read(n);
			write(ask(n));
			putchar('\n');
		}

		cerr<<"COUNT "<<cnt<<endl;
	}
}
bool ED;

signed main(){
	cerr<<"MEM "<<(&ST-&ED)/1024.0/1024<<endl;
	#ifndef ONLINE_JUDGE
	// freopen("pilgrimage.in","r",stdin);
	freopen("pilgrimage6-12.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	LinkWish::mian();
	cerr<<"EXEC TIME: "<<1.0*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}

/usr/bin/ld: /tmp/ccz0Gu91.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwPaPN0.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwPaPN0.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