#include
using namespace std;
#define mInc(x,y) {
x += y;
if (x >= mod)
x -= mod;
}
#define _l (long long int)
const int maxn = 20009; const int mod = 1004535809; const int wo = 3;
int n, m, mz, l, x, a[maxn], g[maxn], ss; int wm, wp[maxn];
int modPow(int a, int x, int tmod = mod) { int s(1); for (; x; x »= 1, a = _l a * a % tmod) if (x & 1) s = _l s * a % tmod; return s; }
void getWM() { static int fm[maxn]; int tf(0); for (int i = 2; i * i <= mz; ++ i) if (mz % i == 0) { fm[tf ++] = i; if (i * i < mz) fm[tf ++] = mz / i; } for (int i = 2; 1; ++ i) { bool ir(1); for (int j = 0; j < tf && ir; ++ j) if (modPow(i, fm[j], m) == 1) ir = 0; if (ir) { wm = i; break; } } for (int i = 0, x = 1; i < mz; ++ i, x = _l x * wm % m) wp[x] = i; }
void fft(int* a, int l, int rv) { for (int i = 1, j = l » 1, k; i < l - 1; ++ i) { if (i < j) swap(a[i], a[j]); for (k = l » 1; j >= k; k »= 1) j -= k; if (j <= k) j += k; } for (int h = 2; h <= l; h «= 1) { int w0(modPow(wo, (mod - 1) / h)); if (rv) w0 = modPow(w0, mod - 2); for (int i = 0; i < l; i += h) { int w(1); for (int j = i; j < i + (h » 1); ++ j) { int x(a[j]), y(_l a[j + (h » 1)] * w % mod); a[j] = (x + y) % mod; a[j + (h » 1)] = (x - y + mod) % mod; w = _l w * w0 % mod; } } } if (rv) { int ni(modPow(l, mod - 2)); for (int i = 0; i < l; ++ i) a[i] = _l a[i] * ni % mod; } }
void conv(int* resa, int* a, int* b) { static int tmp[maxn]; fft(a, l, 0); if (b != a) fft(b, l, 0); for (int i = 0; i < l; ++ i) tmp[i] = _l a[i] * b[i] % mod; fft(tmp, l, 1); for (int i = mz; i < l; ++ i) { mInc(tmp[i % mz], tmp[i]); tmp[i] = 0; } for (int i = 0; i < l; ++ i) resa[i] = tmp[i]; }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
scanf("%d%d%d%d", &n, &m, &x, &ss);
mz = m - 1;
getWM();
memset(a, 0, sizeof(a));
memset(g, 0, sizeof(g));
for (l = 1; l <= m * 2; l <<= 1);
for (int i = 0; i < ss; ++ i) {
int u;
scanf("%d", &u);
if (u)
++ a[wp[u]];
}
g[0] = 1;
for (; n; n >>= 1) {
if (n & 1) {
conv(g, g, a);
fft(a, l, -1);
}
conv(a, a, a);
}
printf("%d\n", g[wp[x]]);
}