题解：

求模素数 p 原根的方法：对 p-1 进行素因子分解，记pi为p-1的第i个因子，若恒有a^((p-1)/pi) mod p ≠ 1  成立，则 a 就是 p 的原根。（对于合数求原根，只需把 p-1 换成 phi(p) 即可）

首先比较暴力是f[i][j]表示前i个，乘积为j

然后是n*m^2的

我们可以利用原根将每个数变成g^x

这样就变成了加和

可以利用生成函数的思想

然后分治+fft就可以了

代码：

#include 
     
      using namespace std;#define rint register int#define rep(i,h,t) for(rint i=h;i<=t;i++)#define dep(i,t,h) for(rint i=t;i>=h;i--)#define IL inlineconst double pi=acos(-1.0);const int N=3e4;int n,m,l,r[N],a[N],b[N],w[N],c[N],g,kk,G=3;int p=1004535809;IL int fsp(int x,int y,int p){  int ans=1;  while (y)  {    if(y&1) ans=1ll*ans*x%p;    x=1ll*x*x%p;    y>>=1;  }  return ans;}IL void jf(int &x,int y){  x+=y;  if (x>p) x-=p;}IL void fft(int *a,int o){  rep(i,0,n-1) if (i>r[i]) swap(a[i],a[r[i]]);  for (int i=1;i
      
       p) x[k]-=p;      }    }  }  if (o==-1)  {    reverse(&a[1],&a[n]);    for (int i=0,inv=fsp(n,p-2,p);i
       
        >n>>m>>x>>s; kk=m-1;  rep(i,1,s) cin>>a[i];  get_g(m);  rep(i,0,m-2) f[fsp(g,i,m)]=i;  m*=2;  rep(i,1,s) if (a[i]) now.a[f[a[i]]]++,c[f[a[i]]]++;  fsp2(n);  cout<<(a[f[x]]+p)%p;  return 0;}