#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

const int N=1000005;
int Tid,mod,inv2,inv4;

int exgcd(int a,int b,ll&x,ll&y)
{
	if(!b){x=1,y=0;return a;}int d=exgcd(b,a%b,x,y);
	int z=x;x=y,y=z-(a/b)*y;return d;
}

inline int Ginv(int a,int b){ll x,y,d=exgcd(a,b,x,y);x=(x%b+b)%b;return x;}
inline void add(int &x,const int &y){x+=y;if(x>=mod)x-=mod;}
inline void dec(int &x,const int &y){x-=y;if(x<0)x+=mod;}
inline int qp(int a,ll n){int b=1;while(n){if(n&1)b=1ll*b*a%mod;a=1ll*a*a%mod,n>>=1;}return b;}

struct Exlucas
{
	int P,PK,mul[N],K,pw[21],fac[N],inv[N];ll G(ll n){if(!n)return 0;return n/P+G(n/P);}
	inline int qp(int a,ll n){int b=1;while(n){if(n&1)b=1ll*b*a%PK;a=1ll*a*a%PK,n>>=1;}return b;}
	int F(ll n)
	{
		if(!n)return 1;ll sq=n/PK;int las=n%PK;
		int w=1ll*qp(mul[PK],sq)*mul[las]%PK,v=F(n/P);return 1ll*w*v%PK;
	}
	inline int Cin(int n,int m){if(n<m||m<0)return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
	int C(ll n,ll m)
	{
		int ans=1;
		while(n>=P)
		{
			ans=1ll*ans*Cin(n%P,m%P)%mod;if(!ans)return 0;
			n/=P,m/=P;
		}
		ans=1ll*ans*Cin(n,m)%mod;return ans;
	}
	inline int Calc(ll n)
	{
		ll p1=G(n*2),p2=G(n);p1-=2*p2;
		if(p1>=K)return 0;
		if(K==1)return C(n*2,n);
		// cout<<p1<<" "<<p2<<'\n';

		int v1=F(n*2),v2=F(n);
		// cout<<v1<<" "<<v2<<'\n';
		
		v2=Ginv(v2,PK);v2=1ll*v2*v2%PK;p1=qp(P,p1);return 1ll*v1*v2%PK*p1%PK;
	}
	inline void init(int _P,int _PK,int _K)
	{
		P=_P,PK=_PK,K=_K;mul[0]=1,pw[0]=1;
		for(int i=1;i<=20;i++)pw[i]=pw[i-1]*P%PK;
		for(int i=1;i<=PK;i++){mul[i]=mul[i-1];if(i%P!=0)mul[i]=1ll*mul[i-1]*i%PK;}
		if(K==1)
		{
			int upd=P-1;fac[0]=1;for(int i=1;i<=upd;i++)fac[i]=1ll*fac[i-1]*i%P;
			inv[upd]=qp(fac[upd],P-2);for(int i=upd-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
			return ;
		}
	}
}W[9];int cnt,a[9],m[9],t[9];

namespace cul8r
{
	inline void init()
	{
		int res=mod;
		for(int i=2;i*i<=res;i++)
		{
			if(res%i!=0)continue;int p=i,pk=1,k=0;
			while(res%i==0)pk=pk*i,res/=i,k++;cnt++,W[cnt].init(p,pk,k);
		}
		if(res>1)cnt++,W[cnt].init(res,res,1);
		// for(int i=1;i<=cnt;i++)cout<<W[i].P<<' '<<W[i].PK<<'\n';
		for(int i=1;i<=cnt;i++)m[i]=mod/W[i].PK,t[i]=Ginv(m[i],W[i].PK);
	}
};

inline int Calc(ll n)
{
	//C(n*2,n)
	for(int i=1;i<=cnt;i++)a[i]=W[i].Calc(n);int ans=0;
	// for(int i=1;i<=cnt;i++)cout<<a[i]<<' ';cout<<'\n';
	for(int i=1;i<=cnt;i++)
	{
		add(ans,1ll*a[i]*m[i]%mod*t[i]%mod);
	}
	return ans;
}

void init(int Testid,int Modulo)
{
	Tid=Testid,mod=Modulo;
	inv2=Ginv(2,mod),inv4=Ginv(4,mod);cul8r::init();
	assert(2*inv2%mod==1&&4*inv4%mod==1);
}

int ask(ll n)
{
	int ans=0,mid=Calc(n),all=qp(2,n*2);

	dec(all,mid);all=1ll*all*inv2%mod;
	add(ans,1ll*n%mod*(all+mid)%mod);
	dec(ans,1ll*n%mod*2%mod*qp(2,n*2-2)%mod);

	ans=ans*2%mod;ans=1ll*ans*qp(inv4,n)%mod;
	return ans;
}

signed main ()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int o, T, p;
	cin >> o >> T >> p;
	init(o, p);
	for (int i = 1; i <= T; i++)
	{
		long long n;
		cin >> n;
		cout << ask(n) << '\n';
	}
	return 0;
}

/usr/bin/ld: /tmp/cc7TDQmz.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2N2g0B.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status