本地直接RE,IDE说MLE，感觉没开很大内存啊。

bool _Start;
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define Tp template<typename T>
#define Ts template<typename T,typename... _T>
Tp il void read(T& x) {
	x=0;bool f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}Ts il void read(T& x,_T&... y) {read(x),read(y...);}
const int N=8010,mod=1004535809;
using ll=long long;
ll n,m,K,S;
ll a[N],tot[N];
il ll qpow(ll a,ll b) {
	ll res=1;
	for(;b;b>>=1,a=a*a%m)
		if(b&1) res=res*a%m;
	return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(b==0) return x=1,y=0,a;
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
struct matrix {
	ll a[N][N];
	matrix(int n=0) {
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++) a[i][i]=1;
	}
	ll* operator[](int x) {return a[x];}
	friend matrix operator*(matrix A,matrix B) {
		matrix C=matrix();
		for(int i=1;i<=m;i++)
			for(int j=1;j<=m;j++)
				for(int k=1;k<=m;k++)
					C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;
		return C;
	}
}bs,f;
il matrix mqpow(matrix A,ll b) {
	matrix res=matrix(m);
	for(;b;b>>=1,A=A*A)
		if(b&1) res=res*A;
	return res;
}
bool _End;
int main() {
	fprintf(stderr,"Memory: %.4lf Mib\n",abs(&_End-&_Start)/1048576.0);
	read(n,m,K,S);
	for(int i=1;i<=S;i++) read(a[i]);
	for(int i=1;i<=S;i++) tot[qpow(a[i],m-2)]++;
	for(int i=1;i<=m;i++) bs[0][i]=tot[0];
	for(int i=2;i<=m;i++) {
		for(int j=1;j<=m;j++) {
			ll x,y;
			exgcd(j,m,x,y);
			x=(x%m+m)%m;
			bs[i][j]=tot[x*(i-1)%m];
		}
	}
	bs=mqpow(bs,n);
	f[1][1]=1;
	f=bs*f;
	printf("%lld",f[K+1][1]);
	return 0;
}