#include <bits/stdc++.h>

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int qpow(int x,int y,int mod)

{

    int res=1;

    while(y)

    {

        if(y&1)   res=1ll*res*x%mod;

        x=1ll*x*x%mod;

        y>>=1;

    }

    return res;

}

const int Mod=1004535809,G=3,iG=qpow(G,Mod-2,Mod),MAX_M=300000;

int fact[10000];

int GetRoot(int x)

{

    int tot=0;

    int phi=x-1;

    for(int i=2;i*i<=phi;++i)     if(phi%i==0) { fact[++tot]=i; while(phi%i==0)  phi/=i;  }

    if(phi>1)   fact[++tot]=phi;

    phi=x-1;

    for(int i=2;i<=phi;++i)

    {

        bool flag=1;

        for(int j=1;j<=tot&&flag;++j)

            if(qpow(i,phi/fact[j],x)==1)   flag=0;

        if(flag)  return i;

    }

    return -1;

}

int limit,rev[MAX_M];

void NTT(int *p,int op)

{

    for(int i=0;i<limit;++i)  if(i<rev[i])   swap(p[i],p[rev[i]]);

    for(int i=1;i<limit;i<<=1)

    {

        int rot=qpow(op==1?G:iG,(Mod-1)/(i<<1),Mod);

        for(int j=0;j<limit;j+=(i<<1))

        {

            int w=1;

            for(int k=0;k<i;++k,w=1ll*w*rot%Mod)

            {

                int x=p[j+k],y=1ll*w*p[i+k+j]%Mod;

                p[j+k]=(x+y)%Mod,  p[i+j+k]=(x-y+Mod)%Mod;

            }

        }

    }

    if(op==-1)

    {

        int inv=qpow(limit,Mod-2,Mod);

        for(int i=0;i<limit;++i)    p[i]=1ll*p[i]*inv%Mod;

    }

}

map<int,int>mp;

int N,M,S,X,F[MAX_M],H[MAX_M];

void mul(int *A,int *B,int *C)

{

    static int res[MAX_M],a[MAX_M],b[MAX_M];

    for(int i=0;i<limit;++i)  a[i]=A[i],b[i]=B[i];

    NTT(a,1), NTT(b,1);

    for(int i=0;i<limit;++i)   a[i]=1ll*a[i]*b[i]%Mod;

    NTT(a,-1);

    for(int i=0;i<M-1;++i)    res[i]=(a[i]+a[i+M-1])%Mod;

    for(int i=0;i<M-1;++i)    C[i]=res[i];

}

int main()

{

    // setIO("input");

    scanf("%d%d%d%d",&N,&M,&X,&S);

    int g=GetRoot(M);

    for(int i=0;i<M-1;++i)   mp[qpow(g,i,M)]=i;

    for(int i=1,x;i<=S;++i)

    {

        scanf("%d",&x);

        x%=M;

        if(x)   F[mp[x%M]]++;

    }

    H[mp[1]]=1;

    int p=0;

    for(limit=1;limit<=2*M;limit<<=1,++p);

    for(int i=0;i<limit;++i)   rev[i]=(rev[i>>1]>>1)|((i&1)<<(p-1));

    while(N)

    {

        if(N&1)    mul(H,F,H);

        mul(F,F,F);

        N>>=1;

    }

    printf("%d\n",H[mp[X]]);

    return 0;

}