RT，调了一下午了

#include<bits/stdc++.h>
#define I inline
#define RI register int
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
using namespace std;
const int N=32005,mo=1004535809;
int n,p,m,sz,x,lim=1,a[N],b[N],r[N],cnt[N],lg[N];
I int add(int a,int b) {
	return a+b>=mo?a+b-mo:a+b;
}
I int sub(int a,int b) {
	return a-b<0?a-b+mo:a-b;
}
I int mul(int a,int b) {
	return 1ll*a*b%mo;
}
I int fast(int a,int b,int mo) {
	RI sum=1;
	while(b) {
		if(b&1) sum=mul(sum,a);
		a=mul(a,a);
		b>>=1;
	}
	return sum;
}
I void NTT(int a[],int lim,int op) {
	rep(i,1,lim-1) if(r[i]>i) swap(a[r[i]],a[i]);
	for(RI i=1; i<lim; i<<=1) {
		RI now=fast(op==1?3:334845270,(mo-1)/(i<<1),mo);
		for(RI j=0; j<lim; j+=(i<<1)) {
			RI res=1;
			rep(k,0,i-1) {
				RI x=a[j+k],y=mul(res,a[j+k+i]);
				a[j+k]=add(x,y),a[j+k+i]=sub(x,y),res=mul(res,now);
			}
		}
	}
	RI now=fast(lim,mo-2,mo);
	rep(i,0,lim-1) if(op==-1) a[i]=mul(a[i],now);
}
I int Root(int n) {
	rep(i,1,1000) {
		memset(cnt,0,sizeof(cnt));
		RI now=1;
		bool flag=1;
		rep(j,1,n-1) cnt[now=now*i%n]?flag=0:cnt[now]=1;
		if(flag) return i;
	}
}
I void fast_pow(int a[],int n) {
	b[lg[1]]=1;
	while(n) {
		if(n&1) {
			NTT(a,lim,1),NTT(b,lim,1);
			rep(i,0,lim-1) b[i]=mul(b[i],a[i]);
			NTT(a,lim,-1),NTT(b,lim,-1);
			rep(i,0,m-2) b[i]=add(b[i],b[i+m-1]);
			rep(i,m-1,lim-1) b[i]=0;
		}
		NTT(a,lim,1);
		rep(i,0,lim-1) a[i]=mul(a[i],a[i]);
		NTT(a,lim,-1);
		rep(i,0,m-2) a[i]=add(a[i],a[i+m-1]);
		rep(i,m-1,lim-1) a[i]=0;
		n>>=1;
	}
}
int main() {
	freopen("a.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&x,&sz);
	p=Root(m);
	RI res=1;
	rep(i,1,m-2)lg[res=res*p%m]=i;
	lg[1]=0;
	RI x;
	rep(i,1,sz) scanf("%d",&x),x&&a[lg[x]]++;
	while(lim<=(m<<1)) lim<<=1;
	rep(i,1,lim-1)r[i]=(r[i>>1]>>1)|((i&1)*(lim>>1));
	fast_pow(a,n);
	return printf("%d\n",b[lg[x]]),0;
}