#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 1004535809;
const ll g = 3;
int rev[16384];
void get_inv() {
	for (int i = 1; i < 16384; i++) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << 13);
	}
}
void swap(ll & a, ll & b) {
	a ^= b ^= a ^= b;
}
ll pow(ll a, ll b, ll p = mod) {
	ll ans = 1;
	while (b != 0) {
		if ((b & 1) == 1) {
			ans = ans * a % p;
		}
		a = a * a % p;
		b = b / 2;
	}
	return ans;
}
struct Poly {
	ll val[16384];
	Poly() {
		for (int i = 0; i < 16384; i++) {
			val[i] = 0;
		}
	}
	void NTT(int inv) {
		for (int i = 0; i < 16384; i++) {
			if (i < rev[i]) {
				swap(val[i], val[rev[i]]);
			}
		}
		for (int mid = 1; mid < 16384; mid <<= 1) {
			ll temp = pow(g, (mod - 1) / (2 * mid));
			if (inv == -1) {
				temp = pow(temp, mod - 2);
			}
			for (int i = 0; i < 16384; i += 2 * mid) {
				ll w = 1;
				for (int j = 0; j < mid; j++, w = w * temp % mod) {
					ll x = val[i + j];
					ll y = w * val[i + j + mid] % mod;
					val[i + j] = (x + y) % mod;
					val[i + j + mid] = (x - y + mod) % mod;
				}
			}
		}
		if (inv == -1) {
			ll inv_length = pow(16384, mod - 2, mod);
			for (int i = 0; i < 16384; i++) {
				val[i] = val[i] * inv_length % mod;
			}
		}
	}
};
Poly mul(Poly a, Poly b, int m) {
	a.NTT(1);
	b.NTT(1);
	Poly c;
	for (int i = 0; i < 16384; i++) {
		c.val[i] = a.val[i] * b.val[i] % mod;
	}
	c.NTT(-1);
	for (int i = m; i < 16384; i++) {
		c.val[i % m] = (c.val[i % m] + c.val[i]) % mod;
		c.val[i] = 0;
	}
	return c;
}
Poly pow(Poly a, ll b, int m) {
	Poly ans;
	ans.val[0] = 1;
	while (b != 0) {
		if ((b & 1) == 1) {
			ans = mul(ans, a, m);
		}
		a = mul(a, a, m);
		b = b / 2;
	}
	return ans;
}
int prime_factor[100];
int get_g(int p) {
	int x = p - 1;
	int cnt = 0;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			cnt++;
			prime_factor[cnt] = i;
			while (x % i == 0) {
				x /= i;
			}
		}
	}
	if (x > 1) {
		cnt++;
		prime_factor[cnt] = x;
	}
	for (int g = 1; ; g++) {
		bool flag = true;
		for (int i = 1; i <= cnt; i++) {
			if (pow(g, (p - 1) / 2, p) == 1) {
				flag = false;
				break;
			}
		}
		if (flag) {
			return g;
		}
	}
}
int table[8005];
int main() {
	get_inv();
	int n, m, x, k;
	scanf("%d %d %d %d", &n, &m, &x, &k);
	int g = get_g(m);
	for (int now = 1, i = 0; i < m - 1; i++, now = now * g % m) {
		table[now] = i;
	}
	Poly A;
	for (int i = 1, r; i <= k; i++) {
		scanf("%d", &r);
		if (r != 0) {
			A.val[table[r]] = 1;
		}
	}
	A = pow(A, n, m - 1);
	printf("%lld", A.val[table[x]]);
	return 0;
}