思路：
普通的DP很好想吧
f[i][j]+=f[i-1][j*s[k]] 前i个数 mod m=j 的个数
m是质数 模数是质数 这就很有趣了
那么我们就求出来原根 所有的数都取指数
搞出生成函数
乘法就变成了加法
快速幂+$NTT$就好了
（注意特判零）
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int mod=1004535809;
int N,M,X,S,n,L,s[8888],R[16385],fst[16385],b[16385],temp1[16385],temp2[16385],inv[8888],vis[8888],prime[8888],tot;
int pow(int x,int y,int p){
int res=1;
while(y){
if(y&1)res=res*x%p;
x=x*x%p,y>>=1;
}return res;
}
void NTT(int *a,int f){
for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
for(int l=1;l<n;l<<=1){
int wn=pow(3,((mod-1)/(l<<1)*f+mod-1)%(mod-1),mod);
for(int j=0;j<n;j+=(l<<1)){
int w=1;
for(int k=0;k<l;k++,w=w*wn%mod){
int x=a[j+k],y=w*a[j+k+l]%mod;
a[j+k]=(x+y)%mod,a[j+k+l]=(x-y+mod)%mod;
}
}
}
if(f==-1){
int Ni=pow(n,mod-2,mod);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*Ni%mod;
}
}
void mul(int *c,int *x,int *y){
for(int i=0;i<n;i++)temp1[i]=x[i],temp2[i]=y[i];
NTT(temp1,1),NTT(temp2,1);
for(int i=0;i<n;i++)c[i]=temp1[i]*temp2[i]%mod;
NTT(c,-1);
for(int i=n-1;i>=M-1;i--)(c[i-M+1]+=c[i])%=mod,c[i]=0;
}
int get_root(){
for(int i=2;;i++){
for(int j=2;j*j<=M;j++)if((M-1)%j==0&&pow(i,(M-1)/j,M)==1)goto ed;
return i;ed:;
}
}
signed main(){
scanf("%lld%lld%lld%lld",&N,&M,&X,&S);
for(n=1;n<=M*2;n<<=1)L++;
for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
int now=1,G=get_root();
for(int i=0;i<M-1;i++)inv[now]=i,(now*=G)%=M;
for(int i=1;i<=S;i++){
scanf("%lld",&s[i]);
if(s[i])fst[inv[s[i]]]=1;
}b[0]=1;
while(N){
if(N&1)mul(b,fst,b);
mul(fst,fst,fst),N>>=1;
}
printf("%lld\n",b[inv[X]]);
}