思路：

普通的DP很好想吧

f[i][j]+=f[i-1][j*s[k]]  前i个数  mod m=j 的个数

 

m是质数  模数是质数  这就很有趣了

那么我们就求出来原根  所有的数都取指数

搞出生成函数

乘法就变成了加法

快速幂+$NTT$就好了

（注意特判零）

//By SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define int long longconst int mod=1004535809;int N,M,X,S,n,L,s[8888],R[16385],fst[16385],b[16385],temp1[16385],temp2[16385],inv[8888],vis[8888],prime[8888],tot;int pow(int x,int y,int p){    int res=1;    while(y){        if(y&1)res=res*x%p;        x=x*x%p,y>>=1;    }return res;}void NTT(int *a,int f){    for(int i=0;i
        
         
          =M-1;i--)(c[i-M+1]+=c[i])%=mod,c[i]=0;}int get_root(){    for(int i=2;;i++){        for(int j=2;j*j<=M;j++)if((M-1)%j==0&&pow(i,(M-1)/j,M)==1)goto ed;        return i;ed:;    }}signed main(){    scanf("%lld%lld%lld%lld",&N,&M,&X,&S);    for(n=1;n<=M*2;n<<=1)L++;    for(int i=0;i
          
           >1]>>1)|((i&1)<<(L-1)); int now=1,G=get_root(); for(int i=0;i
           
            >=1; } printf("%lld\n",b[inv[X]]);}