#include<bits/stdc++.h>
using namespace std;
int s1,s[10005],ind[10005];
long long w,wn,f[50005],g[50005],a1[50005],a2[50005];
const long long G=3,mod=1004535809;
long long mi(long long t,long long v){
    if(!v) return 1;
    long long re=mi(t,v/2);
    re=re*re%mod;
    if(v&1) re=re*t%mod;
    return re;
}
void ch(long long *a,int l){
    for(int i=1,j=l/2;i<l-1;i++){
        if(i<j) swap(a[i],a[j]);
        int k=l/2;
        while(j>=k){
            j-=k;k>>=1;
        }
        j+=k;
    }
}
void ntt(long long *a,int l,int fl){
    for(int i=2;i<=l;i<<=1){
        if(fl==1) wn=mi(G,(mod-1)/i);
        else wn=mi(G,mod-1-(mod-1)/i);
        for(int j=0;j<l;j+=i){
            w=1;
            for(int k=j;k<j+i/2;k++,w=w*wn%mod){
                long long t=a[k],u=w*a[k+i/2]%mod;
                a[k]=(t+u)%mod;
                a[k+i/2]=(t-u+mod)%mod;
            }
        }
    }
    if(fl==-1){
        long long ny=mi(l,mod-2);
        for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;
    }
}
void dd(long long *v1,long long *v2,int l){
    int len=1;
    while(len<2*l) len<<=1;
    for(int i=0;i<l;i++){
        a1[i]=v1[i];a2[i]=v2[i];
    }
    for(int i=l;i<len;i++) a1[i]=a2[i]=0;
    ch(a1,len);ch(a2,len);
    ntt(a1,len,1);ntt(a2,len,1);
    for(int i=0;i<len;i++) a1[i]=a1[i]*a2[i]%mod;
    ch(a1,len);
    ntt(a1,len,-1);
    for(int i=0;i<len;i++) v1[i]=0;
    for(int i=0;i<len;i++) v1[i%(l-1)]=(v1[i%(l-1)]+a1[i])%mod;
}
int find(int e){
    for(int i=2;i<=e;i++){
        for(int j=1,l=i;j<=e;j++,l=l*i%e){
            if(l==1){
                if(j==e-1) return i;
                break;
            }
        }
    }
}
void ksm(int t,int l){
    for(;t;t>>=1){
        if(t&1) dd(f,g,l);
        dd(g,g,l);
    }
}
int main()
{
    int n,m,x;
    scanf("%d%d%d%d",&n,&m,&x,&s1);
    int gt=find(m);
    for(int i=0,l=1;i<m-1;i++){
        ind[l]=i;
        l=l*gt%m;
    }
    for(int i=1;i<=s1;i++){
        scanf("%d",&s[i]);
        if(s[i]==0){
            --i;--s1;continue;
        }
        s[i]=ind[s[i]];
        ++g[s[i]];
    }
    f[0]=1;
    ksm(n,m);
    printf("%lld",f[ind[x]]);
    return 0;
}