## 【BZOJ 3992】[SDOI2015] 序列统计

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 9000;
const int M = N << 2;
const int MOD = 1004535809;

int l,n,m,x,pos[N];

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t, int mod) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%mod)
if (t & 1) ret = (LL)ret * w % mod;
return ret;
}

inline int Get_Primitive_Root(int w) {
vector<int> pri; int cur = w - 1;
for (int i=2,lim=ceil(sqrt(w));i<=cur&&i<=lim;i++) {
if (cur % i == 0) {
pri.push_back(i);
while (cur % i == 0) cur /= i;
}
}
if (cur > 1) pri.push_back(cur);
if (pri.empty()) return 2;
for (int i=2;;i++) {
for (int j=pri.size()-1;j>=0;j--) {
if (Pow(i, w/pri[j], w) == 1) break;
if (!j) return i;
}
}
}

struct Sequence{
int a[M],POS[M],len;
inline Sequence() {}
inline Sequence(int l) {
memset(a,0,sizeof(a));
len = l; a[0] = 1;
}
inline Sequence(Sequence &B) {
memcpy(this, &B, sizeof(B));
len=B.len;
}
inline void NTT(int f) {
static const int G = Get_Primitive_Root(MOD);
int l = -1; for (int i=len;i;i>>=1) l++;
if (!POS[1]) {
for (int i=1;i<len;i++) {
POS[i] = POS[i>>1]>>1;
if (i & 1) POS[i] |= 1 << l-1;
}
}
for (int i=0;i<len;i++) if (POS[i] > i)
swap(a[i], a[POS[i]]);
for (int seg=2;seg<=len;seg<<=1) {
int wn = Pow(G, MOD/seg, MOD);
if (f == -1) wn = Pow(wn, MOD-2, MOD);
for (int i=0;i<len;i+=seg) {
for (int k=i,w=1;k<i+seg/2;k++,w=(LL)w*wn%MOD) {
int tmp = (LL)w * a[k+seg/2] % MOD;
a[k+seg/2] = ((a[k] - tmp) % MOD + MOD) % MOD;
a[k] = (a[k] + tmp) % MOD;
}
}
}
if (f == -1) {
for (int i=0,rev=Pow(len,MOD-2,MOD);i<len;i++)
a[i] = (LL)a[i] * rev % MOD;
}
}
inline void Multiply(Sequence B) {
NTT(1); B.NTT(1);
for (int i=0;i<len;i++)
a[i] = (LL)a[i] * B.a[i] % MOD;
NTT(-1);
for (int i=m-1;i<len;i++)
(a[i-m+1] += a[i]) %= MOD, a[i] = 0;
}
inline void pow(int t) {
Sequence ret(len),w(*this);
for (;t;t>>=1,w.Multiply(w))
if (t & 1) ret.Multiply(w);
memcpy(this, &ret, sizeof(ret));
}
}arr;

int main() {
l = read(); m = read();
x = read() % m; n = read();
int PRT = Get_Primitive_Root(m);
for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0;
int len = 1; while (len < m) len <<= 1;
arr.len = len << 1; arr.pow(l);
printf("%d\n",(arr.a[pos[x]]+MOD)%MOD);
return 0;
}