【题目描述】
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题 的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
【输入格式】
一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。
第二行，|S|个整数，表示集合S中的所有元素。
【输出格式】
一行，一个整数，表示你求出的权值和mod 1004535809的值。
【样例输入】
4 3 1 2
1 2
【样例输出】
8
【提示】
对于10%的数据，1<=N<=1000；
对于30%的数据，3<=M<=100；
对于60%的数据，3<=M<=800；
对于全部的数据，1<=N<=10^9，3<=M<=8000，M为质数，0<=x<=M-1，输入数据保证集合S中元素不重复。
竟然没有x=0的数据。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=,G=;
const int MOD=;
int g,n,m,x,s,pos[N],num[N];
int Qpow(int x,int k,int mod){
long long ret=;
while(k){
if(k&)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;k>>=;
}
return ret;
} void Rader(int *a,int len){
for(int i=,j=len>>;i<len-;i++){
if(i<j)swap(a[i],a[j]);
int k=len>>;
while(j>=k){
j-=k;
k>>=;
}
j+=k;
}
} void NTT(int *a,int len,int on){
Rader(a,len);
for(int h=,wn;h<=len;h<<=){
if(on==)wn=Qpow(G,(MOD-)/h,MOD);
else wn=Qpow(G,MOD--(MOD-)/h,MOD);
for(int j=;j<len;j+=h){
int w=,x,y;
for(int k=j;k<j+(h>>);k++){
x=a[k];y=1ll*a[k+(h>>)]*w%MOD;
a[k]=(x+y)%MOD;a[k+(h>>)]=(x-y+MOD)%MOD;
w=1ll*w*wn%MOD;
}
}
}
if(on==-){
int inv=Qpow(len,MOD-,MOD);
for(int i=;i<len;i++)
a[i]=1ll*a[i]*inv%MOD;
}
} int f[N],r[N],l=N/;
void Solve(){
for(int i=;i<N;i++)
r[i]=f[i];n-=;
while(n){
NTT(f,N,);
if(n&){
NTT(r,N,);
for(int i=;i<N;i++)r[i]=1ll*r[i]*f[i]%MOD;
NTT(r,N,-);
for(int i=m-;i<N;i++)(r[i%(m-)]+=r[i])%=MOD,r[i]=;
}
for(int i=;i<N;i++)f[i]=1ll*f[i]*f[i]%MOD;
NTT(f,N,-);
for(int i=m-;i<N;i++)(f[i%(m-)]+=f[i])%=MOD,f[i]=;
n>>=;
}
printf("%d\n",r[pos[x]]);
} void Solve_Zero(){int cnt=,ans;
for(int i=;i<=s;i++)if(!num[i])cnt++;
ans=Qpow(s,n,MOD)-Qpow(s-cnt,n,MOD);
printf("%d\n",ans);
}
int main(){
freopen("sdoi2015_sequence.in","r",stdin);
freopen("sdoi2015_sequence.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&x,&s);
for(int i=;i<=s;i++)
scanf("%d",&num[i]);
if(!x)Solve_Zero();
for(g=;g<m;g++){int i;
for(i=;i<m-;i++)
if(Qpow(g,i,m)==)
break;
if(i==m-&&Qpow(g,m-,m)==)break;
}
for(int i=;i<m;i++)
pos[Qpow(g,i,m)]=i%(m-);
for(int i=;i<=s;i++)
if(num[i])f[pos[num[i]]]++;
Solve();
return ;
}