#include<bits/stdc++.h>
#include "pilgrimage.h"
using namespace std;
#define N 1000009
inline long long read()
{
    register long long x=0;
    register char ch=cin.get();
    register bool op=0;
    while(!isdigit(ch)) {if(ch=='-')op=1;ch=cin.get();}
    while(isdigit(ch)) {(x*=10)+=(ch^48);ch=cin.get();}
    return op? -x:x;
}
long long x,y,p,n,o,T;
long long ans;
inline void exgcd(register long long a,register long long b)
{
    if(!b) {x=1,y=0;return;}
    exgcd(b,a%b);
    int nx=x;
    x=y;
    y=nx-a/b*y;
}
long long inv[N];
inline long long INV(register long long k)
{
    if(inv[k]) return inv[k];
    x=0,y=0;
    exgcd(k,p);
    inv[k]=(x%p+p)%p;
    return inv[k];
}
inline void dfs(register long long a,register int cnt,register int w)
{
    if(cnt==n) return ans+=a*abs(w),void();
    for(register int i(1);i<=3;++i) 
    {
        if(i==1) dfs(a*INV(4)%p,cnt+1,w-1);
        if(i==2) dfs(a*INV(2)%p,cnt+1,w);
        if(i==3) dfs(a*INV(4)%p,cnt+1,w+1);
    }
}
inline void init(int o,int p){ans=0;}
inline int ask(long long n)
{
    ans=0;
    dfs(1,0,0);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    // freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    o=read();T=read();p=read();init(0,0);
    for(register int i(1);i<=T;++i) 
    {
        n=read();
        printf("%lld\n", ask(n)%p);
    }
    return 0;
}

/usr/bin/ld: /tmp/ccorlElO.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cc72xj7O.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc72xj7O.o: in function `main':
implementer.cpp:(.text.startup+0x2b): undefined reference to `init(int, int)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x16c): undefined reference to `ask(long long)'
collect2: error: ld returned 1 exit status