Description

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

 

Input

一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。

第二行，|S|个整数，表示集合S中的所有元素。

Output

一行，一个整数，表示你求出的权值和mod 1004535809的值。

 

Sample Input

4 3 1 2 1 2

Sample Output

8 【样例说明】 可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。

 

Data Constraint

对于10%的数据，1<=N<=1000；

对于30%的数据，3<=M<=100；

对于60%的数据，3<=M<=800；

对于全部的数据，1<=N<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复。

 

 

解法：

首先可以想到一个暴力dp，设f[i][j]表示选到第i个数，mod m=j的方案数。那么显然转移方程为f[i+1][j*k%m]+=f[i][j];

即f[i+1][j*k%m]=∑f[i][j]*num[k]（序列S中mod m=k的数的个数）

因为m是质数，所以m存在原根，我们可以通过离散对数的变换将乘法变为加法

原式变为f[i+1][(ind[j]+ind[k])%(m-1)]=∑f[i][ind[j]]*num[ind[k]]

为卷积形式，可使用FFT优化。

N很大，所以套一个快速幂即可

 

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;int n,m,x,L,i,k,N,ws,NN;int a[100011],pos[100011],b[100011],B[100011],d[100011];int w[100011],ind[100011],h[100011];int mo=1004535809;int mi(int x,int z){    int l;    l=1;    while(z){        if(z%2==1)l=(ll)l*x%mo;        z/=2;        x=(ll)x*x%mo;    }    return l;}bool isroot(int x){    int i,l;    l=1;    for(i=1;i
          
           0)?w[i<<(ws-l)]:w[N-(i<<(ws-l))]; for(j=i;j
           
            <