#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

typedef __uint128_t u128;

int TOT;

char _buf[1<<26],*iS=_buf-1;
#define getchar() (*iS++)
inline int read(){
	char ch=' '; int x=0;
	do{
		ch=getchar();
	}while(ch<'0' || ch>'9');
	do{
		x=x*10+ch-'0';
		ch=getchar();
	}while(ch>='0' && ch<='9');
	return x;
}

void exgcd(int &x,int &y,int a,int b){
	if(!b){
		x=1, y=0;
		return;
	}
	exgcd(x, y, b, a%b);
	// bx+(a-a/b*b)y
	int t=x;
	x=y, y=t-a/b*y;
}
int inv(int x,int mod){
	int t0,t1;
	exgcd(t0,t1,x,mod);
	return (t0%mod+mod)%mod;
}

const int N=1e6+5;

struct Sub{
	int mod,p;
	
	u128 T,T0; int lg,lg0;
	inline int Div(const int &x){
		return T*x>>lg;
	}
	inline int Mod(const int &x){
		return x-mod*Div(x);
	}
	
	struct Int{
		int w,c;
		Int(int x=0){w=x, c=0;}
		Int(int _w, int _c){
			w=_w, c=_c;
		}
	};
	inline Int mul(const Int &A,const Int &B){
		return (Int){ Mod(A.w*B.w), A.c+B.c};
	}
	int qpow(int x,int y){
		int res=1;
		while(y){
			if(y%2) res=Mod(res*x);
			x=Mod(x*x);
			y/=2;
		}
		return res;
	}int inv(int x){return qpow(x, mod/p*(p-1)-1);}

	vector<Int> fac;
	void init(int _mod){
		mod=_mod;
		
		p=0;
		rep(i,2,mod){
			if(mod%i==0){
				p=i;
				break;
			}
		}
		assert(p!=0);
		
		lg=__lg(mod)+64;
		T=(((u128)1<<lg)+mod-1)/mod;
		
		fac.resize(mod);
		fac[0]=1;
		rep(i,1,mod-1){
			if(i%p==0){
				fac[i]=fac[i-1];
			}
			else{
				fac[i]=mul(fac[i-1], i);
			}
		}
	}
	Int Fac(int x){
		Int res=1;
		while(x>=p){
			int nxt=x/p;
			Int c=(Int){ (Div(x)%2? mod-1: 1), nxt}, g=fac[Mod(x)];
			res=(Int){ Mod(c.w*g.w*res.w), c.c+g.c+res.c};
			x=nxt;
		}
		res=mul(res, fac[x]);
		return res;
	}
	int C(int n){
		Int a=Fac(n*2), b=Fac(n);
		Int pr={Mod( a.w*inv( Mod(b.w*b.w) ) ), a.c-b.c*2};
		int res=pr.w;
		while(res && pr.c){
			pr.c--;
			(res*= p )%=mod;
		}
		return res;
	}
};


int mod, phimod, i4;
int qpow(int x,int y){
	if(y>=phimod){
		y%=phimod;
	}
	int res=1;
	while(y){
		if(y%2) res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}
vi Mod, K;
vector< Sub > S;
void init(){
	i4=inv(4,mod);
	phimod=mod;
	int tmp=mod;
	for(int i=2;i*i<=tmp;i++){
		if(tmp%i==0){
			phimod=phimod/i*(i-1);
			Mod.pb(1);
			while(tmp%i==0){
				Mod.back()*=i;
				tmp/=i;
			}
		}
	}
	if(tmp!=1){
		phimod=phimod/tmp*(tmp-1);
		Mod.pb(tmp);
	}
	rep(i,0,(int)Mod.size()-1){
		K.pb( (mod/Mod[i])*inv(mod/Mod[i],Mod[i])%mod );
	}
	rep(i,0,(int)Mod.size()-1){
		S.pb({});
		S[i].init(Mod[i]);
	}
}
void solve(){
	int n=read();
	int res=0;
	rep(i,0,(int)Mod.size()-1){
		(res+= K[i]*S[i].C(n) )%=mod;
	}
	res= n%mod*res%mod*qpow(i4,n)%mod; 
	cout<<res<<'\n';
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	fread(_buf,1,1<<26,stdin);
	
	int _o=read(), t=read();
	mod=read();
	init();
	while(t--){
		solve();
	}
	cerr<<TOT<<endl;
}

answer.code: In function ‘int main()’:
answer.code:184:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  184 |         fread(_buf,1,1<<26,stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccdZ7Gdm.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccFVU9ym.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccFVU9ym.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