一道不错的多项式好题。还涉及了一些数论内容。
首先我们看到题目是求乘积模(m)的方案数，考虑到这种方案数我们一般都可以用生成函数来做。
但显然卷积的下标有加（FFT,NTT等）有位运算（FWT）但是没有乘法的。除非您十分dalao自己发明一个卷积算法
所以我们考虑化乘为加，我们注意到(m)是一个不大的指数，那么意味这我们可以利用同余系下的一大利器——原根
关于原根的主要性质，其实就是原根(g)，满足(g^0,g^1dots g^{m-2})模(m)后各不相同。
所以我们可以暴力找出原根（可以参考dalao's blog），然后把每一个数转化为原根的幂指数
这样我们把两个数相乘时其实就是指数相加，那么直接多项式快速幂即可。
但是注意到这里的下标其实是在模意义下的，并且根据欧拉定理我们还可以知道指数模的是(m-1)（不是(m)！），这个我们在做完NTT时把跑到后面的项手动加到前面去就可以了。
复杂度(O(mlog^2 n))，实测跑得非常快。
CODE
#include<cstdio>
#define RI register int
using namespace std;
const int M=8005,mod=1004535809;
int n,m,tar,s,t,x,root,A[M<<2],rg[M],rst[M],cnt;
inline int quick_pow(int x,int r,int p=mod,int mul=1)
{
for (;r;r>>=1,x=1LL*x*x%p) if (r&1) mul=1LL*mul*x%p; return mul;
}
inline int get_root(int x)
{
RI i; for (i=2;i<=x-2;++i) if ((x-1)%i==0)
rg[++cnt]=i; for (i=2;;++i)
{
bool flag=1; for (RI j=1;j<=cnt;++j)
if (quick_pow(i,rg[j],x)==1) { flag=0; break; }
if (flag) return i;
}
}
inline void inc(int& x,int y)
{
if ((x+=y)>=mod) x-=mod;
}
inline void dec(int& x,int y)
{
if ((x-=y)<0) x+=mod;
}
class Poly_Solver
{
private:
int rev[M<<2],T[M<<2],lim,p;
inline void init(int n)
{
for (lim=1;lim<=n;lim<<=1,++p);
for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);
}
inline void swap(int& x,int& y)
{
int t=x; x=y; y=t;
}
inline void NTT(int *f,int opt)
{
RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);
for (i=1;i<lim;i<<=1)
{
int m=i<<1,D=quick_pow(3,opt==1?(mod-1)/m:mod-1-(mod-1)/m);
for (RI j=0;j<lim;j+=m)
{
int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)
{
int x=f[j+k],y=1LL*f[i+j+k]*W%mod;
f[j+k]=f[i+j+k]=x; inc(f[j+k],y); dec(f[i+j+k],y);
}
}
}
if (opt==-1)
{
int Inv=quick_pow(lim,mod-2);
for (i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;
}
}
inline void mul_self(int *A)
{
RI i; for (NTT(A,1),i=0;i<lim;++i)
A[i]=1LL*A[i]*A[i]%mod;
NTT(A,-1); for (i=lim-1;i>=m-1;--i) inc(A[i-m+1],A[i]),A[i]=0;
}
inline void mul(int *A,int *B)
{
RI i; for (NTT(A,1),NTT(B,1),i=0;i<lim;++i) A[i]=1LL*A[i]*B[i]%mod;
NTT(A,-1); NTT(B,-1); for (i=lim-1;i>=m-1;--i) inc(A[i-m+1],A[i]),A[i]=0;
}
public:
inline int pow(int *A,int r,int tar)
{
for (init(m<<1),T[0]=1;r;r>>=1,mul_self(A))
if (r&1) mul(T,A); return T[tar];
}
}P;
int main()
{
RI i; scanf("%d%d%d%d",&n,&m,&tar,&s); root=get_root(m);
for (x=i=1;i<=m-2;++i) rst[x=1LL*x*root%m]=i;
for (i=1;i<=s;++i) scanf("%d",&x),x&&(A[rst[x]]=1);
return printf("%d
",P.pow(A,n,rst[tar])),0;
}