#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(ll)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(ll)*(n))
const int N=16384;
const ll mod=1004535809;
const ll _G=3;
const ll invg=334845270;
int k,m,x,s;
int tn=0,tr[N<<1],ln[N];
int getg(){
    for (int i=1;i<m;i++){
        int now=1;
        for (int j=1;j<m;j++){
            (now*=i)%=m;
            if (now==1){
                if (j==m-1)return i;
                else break;
            }
        }
    }
}
void init(){
    int g=getg();
    ln[1]=0;int now=1;
    for (int i=1;i<m;i++){
        (now*=g)%=m;ln[now]=i;
    }
}
void tpre(int n){
    if (n==tn)return ;tn=n;
    for (int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
ll fst(ll x,ll y){
    ll ans=1;
    while(y){
        if (y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }return ans;
}
void NTT(ll *g,int n,bool opt){
    tpre(n);
    static ll f[N<<1],w[N<<1]={1};
    for (int i=0;i<n;i++)f[i]=g[tr[i]];
    for (int p=2;p<=n;p<<=1){
        int len=p>>1;
        ll tG=fst(opt?_G:invg,(mod-1)/p);
        for (int i=1;i<len;i++)w[i]=w[i-1]*tG%mod;
        for (int i=0;i<n;i+=p){
            for (int j=i;j<i+len;j++){
                ll now=f[j+len]*w[j-i]%mod;
                f[j+len]=(f[j]+mod-now)%mod;
                f[j]=(f[j]+now)%mod;
            }
        }
    }
    if (opt)for (int i=0;i<n;i++)g[i]=f[i];
    else{
        ll invn=fst(n,mod-2);
        for (int i=0;i<n;i++)g[i]=f[i]*invn%mod;
    }
}
void px(ll *f,ll *g,int n){
    for (int i=0;i<n;i++)f[i]=f[i]*g[i]%mod;
}
void times(ll *f,ll *g,int len,int lim){
    int n=1;for (;n<=len;n<<=1);
    static ll sav[N<<1];
    clr(sav,n);cpy(sav,g,n);
    NTT(f,n,1);NTT(sav,n,1);
    px(f,sav,n);NTT(f,n,0);
    clr(sav,n);clr(f+lim,n-lim);
}
void upd(ll *f,ll *g,int len){
    int n=1;for (;n<=len;n<<=1);
    times(f,g,2*n,2*len);
    for (int i=0;i<len;i++)f[i]=(f[i]+f[i+len])%mod;
    clr(f+len,2*n-len);
}
ll id[N<<1],ans[N<<1];
int main(){
	freopen ("sdoi2015_sequence.in","r",stdin);
	freopen ("sdoi2015_sequence.out","w",stdout);
	scanf("%d%d%d%d",&k,&m,&x,&s);
	init();
	for (int i=1;i<=s;i++){
	    int t;scanf("%d",&t);
	    if (!t)continue;
	    id[ln[t]%(m-1)]=1;
    }
    ans[0]=1;
    while(k){
        if (k&1)upd(ans,id,m-1);
        upd(id,id,m-1);k>>=1;
    }
    printf("%lld\n",ans[ln[x]%(m-1)]);
}