#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000009
inline int read()
{
    register int 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;
}
int x,y,p,n,o,T;
int ans;
inline void exgcd(register int a,register int b)
{
    if(!b) {x=1,y=0;return;}
    exgcd(b,a%b);
    int nx=x;
    x=y;
    y=nx-a/b*y;
}
int inv[N];
inline int INV(register int 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 int 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(){o=read();T=read();p=read();}
inline void ask()
{
    n=read();
    ans=0;
    dfs(1,0,0);
    printf("%lld\n",ans%p);
}
signed main()
{
    ios::sync_with_stdio(0);
    // freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    init();
    for(register int i(1);i<=T;++i) ask();
    return 0;
}

/usr/bin/ld: /tmp/cc67JGgP.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYRToaO.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYRToaO.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