#include<bits/stdc++.h>

using namespace std;
using E=long long;

E mod,BKSZ;
vector<pair<int,int>> divsp;
vector<int> val,phi;
vector<vector<E>> sum,pw,PW;

E ksm(E a,E b,E MOD){
  //cerr<<"b="<<b<<endl;
  E ret=1;
  a%=MOD;
  while(b){
    if(b&1) ret=ret*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return ret;
}

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

E inverse(E a,E mod){
  //assert(__gcd(a,mod)==1);
  a%=mod;
  //assert(a!=0);
  E X=0,Y=0;
  E d=exgcd(a,mod,X,Y);
  return (X%mod+mod)%mod;
}

E power(int i,E b){
  b%=phi[i];
  return pw[i][b%BKSZ]*PW[i][b/BKSZ]%val[i];
}

E calcu(E n,int i){
  if(n==0) return 1;
  E pq=val[i];
  E ret=sum[i][n%pq];
  ret=ret*power(i,n/pq)%pq;
  ret=ret*calcu(n/divsp[i].first,i)%pq;
  return ret;
}

E get(E n,E p){
  E ret=0;
  __int128 bs=p;
  while(bs<=n){
    ret+=n/bs;
    bs*=p;
  }
  return ret;
}

E C(E n,E m,int i){
  E pq=val[i],p=divsp[i].first;
  return calcu(n,i)*inverse(calcu(m,i),pq)%pq*inverse(calcu(n-m,i),pq)%pq*ksm(p,get(n,p)-get(m,p)-get(n-m,p),pq)%pq;
}

E CRT(E n,E m){
  if(n<0||m<0||n<m) return 0;
  if(n==0||m==0) return 1;
  E ret=0,M=1;
  for(auto p:val) M=M*p;
  for(int i=0; i<(int)divsp.size(); i++){
    E dM=M/val[i];
    E tmp=C(n,m,i);
    ret=(ret+tmp*dM%M*inverse(dM,val[i])%M)%M;
  }
  return ret;
}

void init(int o,int p){
  mod=p;
  for(int i=2; i*i<=p; i++){
    if(p%i) continue;
    int s=0; int x=1;
    while(p%i==0) x*=i,s++,p/=i;
    phi.emplace_back(x/i*(i-1));
    val.emplace_back(x);
    divsp.emplace_back(make_pair(i,s));
  }
  if(p>1){
    phi.emplace_back(p-1);
    val.emplace_back(p);
    divsp.emplace_back(make_pair(p,1));
  }
  BKSZ=sqrt(mod)+1;
  sum.resize(divsp.size());
  PW=pw=sum;
  for(int i=0; i<(int)divsp.size(); i++){
    sum[i]=vector<E>(val[i]);
    sum[i][0]=1;
    for(int j=1; j<val[i]; j++){
      sum[i][j]=sum[i][j-1];
      if(j%divsp[i].first) sum[i][j]=sum[i][j]*j%val[i];
    }
    E bs=sum[i].back();
    pw[i]=vector<E>(BKSZ+1);
    pw[i][0]=1;
    for(int j=1; j<=BKSZ; j++) pw[i][j]=pw[i][j-1]*bs%val[i];
    PW[i]=vector<E>(BKSZ+1); PW[i][0]=1;
    for(int j=1; j<=BKSZ; j++) PW[i][j]=PW[i][j-1]*pw[i][BKSZ]%val[i];
  }

}

int ask(long long n){
  if(n==1) return inverse(2,mod);
  E t1=CRT(2*n-4,n-2)-CRT(2*n-4,n-3)+mod;
  t1%=mod;
  t1=t1*4%mod*(2*n%mod-3)%mod*(2*n%mod-1)%mod;
  t1=t1*ksm(inverse(4,mod),n,mod)%mod;
  return (t1%mod+mod)%mod;
}

int main(){

  int o,T,p;
  cin>>o>>T>>p;
  init(o,p);

  while(T--){
    long long nn;
    cin>>nn;
    cout<<ask(nn)<<'\n';
  }

  return 0;
}

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