#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef __uint128_t L;
struct FastMod{
	ULL b,m;
	FastMod(){}
	FastMod(ULL b):b(b),m(ULL((L(1)<<64)/b)){}
	ULL reduce(ULL a){
		ULL q=(ULL)((L(m)*a)>>64);
		ULL r=a-q*b;
		return r>=b?r-b:r;
	}
}F,G;
int Rf(ll x){return F.reduce(x);}
int Rg(ll x){return G.reduce(x);}
int P,M,tot,pp[30],a[30],b[30],k[30],phi[30],ks[30],ph,mm,gs[30],mmi[2000001];
vector<int> gg[30],inn[30],mii[30];
ll calcfacb(ll ip,int id){
	if(!ip)return 0;
	return calcfacb(ip/b[id],id)+ip/b[id];
}
int ksm(int x,ll y,int mod){
	int z=1;
	for(;y;y>>=1,x=Rf(1ll*x*x))if(y&1)z=Rf(1ll*z*x);
	return z;
}
int calcfacm(ll ip,int id){
	if(!ip)return 1;
	return Rf(1ll*Rf(1ll*mii[id][(ip/pp[id])%phi[id]]*gg[id][ip%pp[id]])*calcfacm(ip/b[id],id));
//	return 1ll*ksm(gg[id][pp[id]],(ip/pp[id])%phi[id],pp[id])*gg[id][ip%pp[id]]%pp[id]*calcfacm(ip/b[id],id)%pp[id];
}
int C(ll x,ll y,int id){
	int A=calcfacm(x,id);
	A=Rf(1ll*Rf(1ll*A*inn[id][calcfacm(y,id)])*inn[id][calcfacm(x-y,id)]);
//	A=1ll*A*ksm(calcfacm(y,id),phi[id]-1,pp[id])%pp[id]*ksm(calcfacm(x-y,id),phi[id]-1,pp[id])%pp[id];
	ll B=calcfacb(x,id)-calcfacb(y,id)-calcfacb(x-y,id);
	return Rf(1ll*A*ksm(b[id],B,pp[id]));
//	return 1ll*A*ksm(b[id],B,pp[id])%pp[id];
}
void newprime(int i){
	b[++tot]=i,pp[tot]=1;while(!(P%i))k[tot]++,P/=i,pp[tot]*=i;
	phi[tot]=pp[tot]/i*(i-1);
	gg[tot].push_back(1);
	inn[tot].push_back(1);
	F=FastMod(pp[tot]);
	for(int j=1,s=1;j<=pp[tot];j++)
	{
		if(j%i)s=Rf(1ll*s*j);
		gg[tot].push_back(s);
		inn[tot].push_back(ksm(j,phi[tot]-1,pp[tot]));
	}
	mii[tot].push_back(1);
	for(int j=1,s=1;j<=pp[tot];j++)
	{
		s=Rf(1ll*s*gg[tot][pp[tot]]);
		mii[tot].push_back(s);
	}
}
void init(int o,int p)
{
	M=P=p;
	G=FastMod(M);
	for(int i=2;i*i<=P;i++)if(!(P%i))newprime(i);
	if(P!=1)newprime(P);
	for(int i=1;i<=tot;i++)
	{
		ks[i]=1;
		int x=M/pp[i];
		for(int j=1;j<phi[i];j++)ks[i]=Rg(1ll*ks[i]*x);
//		ks[i]=ksm(M/pp[i],phi[i]-1,pp[i]);
	}
	ph=1;
	for(int i=1;i<=tot;i++)ph*=phi[i];
	mm=1;for(int i=1;i<ph;i++)mm=Rg(4ll*mm);
	mmi[0]=1;for(int i=1;i<=2*ph;i++)mmi[i]=Rg(1ll*mm*mmi[i-1]);
}
unordered_map<ll,int> ma;
int ask(long long n)
{
	if(ma[n])return ma[n];
	for(int i=1;i<=tot;i++)F=FastMod(pp[i]),a[i]=C(2*n,n,i);
	int res=0;
	for(int i=1;i<=tot;i++)res=Rg(res+Rg(1ll*Rg(M/pp[i])*Rg(1ll*a[i]*ks[i])));
	res=Rg(1ll*Rg(n)*res);
    ll h=__gcd(n,1ll*ph);
    if(h==1)res=Rg(1ll*res*mmi[n%ph]);
    else if(n>=ph)res=Rg(1ll*res*mmi[n%ph+ph]);
    else res=Rg(1ll*res*mmi[n]);
    return ma[n]=res;
}

signed main ()
{
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	int o, T, p;
	std::cin >> o >> T >> p;
	init(o, p);
	for (int i = 1; i <= T; i++)
	{
		long long n;
		std::cin >> n;
		std::cout << ask(n) << '\n';
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:97:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |         freopen("b.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
answer.code:98:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |         freopen("b.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBwfZtU.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccaHsCYT.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status