考虑dp,$f_i(x)$表示用$i$个数表示出$x$来的方案数
$$ f_i(c) = \sum_{ab \equiv c\pmod m} f_{i / 2}(a) \times f_{i / 2}(b) $$
很像卷积,不过是乘法,需要将$ab$转化为$a+b$
$$ f_i(g^c) = \sum_{a + b \equiv c\pmod {m - 1}} f_{i / 2}(g^a) \times f_{i / 2}(g^b) $$
若$g$为$m$的原根,则$g^a$在模$m$意义下各不相同,可以与$a$形成一一映射关系,于是我们暴力找到一个原根$g$,将$S$中的元素$g^a$改为$a$即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int N = 2e6 + 10, M = 8e3 + 10, mod = 1004535809, inv3 = 334845270;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int n, m, G, S, inv[N], lg[N], lg2[N], f[40][N], W[2][40], rev[40][N], ans[N], a[N], b[N];
bool vis[M];
int MOD(int x) {while (x > mod) x -= mod; while (x < 0) x += mod; return x;}
int power(int a, int x) {
int res = 1;
while (x) {if (x & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; x >>= 1;}
return res;
}
bool check(int x) {
memset(vis, 0, sizeof(vis)); int t = 1;
for (int i = 0; i <= m - 2; i++, t = 1ll * t * x % m) {
if (vis[t]) return 0; vis[t] = 1;
}
return 1;
}
void init() {
int G, t = 1; n = inv[1] = 1; while (n < 2 * m) n <<= 1;
for (int i = 2; i < m; i++) if (check(i)) {G = i; break;}
for (int i = 0; i <= m - 2; i++) lg[t] = i, t = 1ll * t * G % m; m--;
for (int i = 0; 1 << i <= n; i++) lg2[1 << i] = i;
for (int i = 2; i <= n; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for (int i = 0; 1 << i <= n; i++) {
W[0][i] = power(inv3, (mod - 1) / (1 << i + 1));
W[1][i] = power(3, (mod - 1) / (1 << i + 1));
for (int j = 0; j < 1 << i; j++) rev[i][j] = rev[i][j >> 1] >> 1 | (j & 1 ? 1 << i - 1 : 0);
}
}
void ntt(int a[], int opt) {
for (int i = 0; i < n; i++) if (i < rev[lg2[n]][i]) swap(a[i], a[rev[lg2[n]][i]]);
for (int i = 1; i < n; i <<= 1) {
int t = W[opt][lg2[i]];
for (int j = 0; j < n; j += i << 1) {
int w = 1;
for (int k = j; k < j + i; k++) {
int x = a[k], d = 1ll * w * a[k + i] % mod;
a[k] = MOD(x + d); a[k + i] = MOD(x - d); w = 1ll * w * t % mod;
}
}
}
if (!opt) for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv[n] % mod;
}
void mul(int c[], int f[], int g[]) {
memset(a, 0, sizeof(a)); for (int i = 0; i < m; i++) a[i] = f[i];
memset(b, 0, sizeof(b)); for (int i = 0; i < m; i++) b[i] = g[i];
ntt(a, 1); ntt(b, 1);
for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % mod;
ntt(a, 0);
for (int i = 0; i < m; i++) c[i] = a[i];
for (int i = m; i < n; i++) c[i % m] = MOD(c[i % m] + a[i]);
}
void solve(int x) {
ans[0] = 1;
for (int i = 30; i >= 0; i--) if (x >> i & 1) mul(ans, ans, f[i]);
}
signed main() {
int n = read(); m = read(); G = read(); S = read(); init();
for (int i = 1; i <= S; i++) {int x = read(); if (!x) continue; f[0][lg[x]]++;}
for (int i = 1; i <= 30; i++) mul(f[i], f[i - 1], f[i - 1]);
solve(n); printf("%lld", ans[lg[G]]);
return 0;
}