题目链接：

　　我来复习板子了……这道题也是我写的第一发求原根啊？

　　求原根方法：

　　从小到大依次枚举原根。设当前枚举的原根为\(x\)，模数为\(p\)，\(p-1\)的质因数分别为\(p_1,p_2,\dots,p_m\)，则只需检验\(x^{\frac{p-1}{p_i}}\equiv1 \pmod{p}\)是否成立即可。如果成立则\(x\)不是原根。

　　然后这道题朴素\(dp\)就不讲了。设\(m\)的原根为\(g\)，那么把每个数表示成\(g^k\)的形式就可以乘法变加法了，就成为了\(NTT\)板子题，快速幂一下就做完了。注意这道题是循环卷积，记得把多出来的那部分弄到前面去。

　　下面贴代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 100010#define mod 1004535809using namespace std;typedef long long llg;int R[maxn],n,m,N,L,T,rt,pm;int a[maxn],b[maxn],c[maxn];bool vis[maxn];int getint(){ int w=0;bool q=0; char c=getchar(); while((c>'9'||c<'0')&&c!='-') c=getchar(); if(c=='-') c=getchar(),q=1; while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;}int qpow(int x,int y,int c){ int s=1; while(y){ if(y&1) s=1ll*s*x%c; x=1ll*x*x%c; y>>=1; } return s;}void root(int p){ if(p==2){rt=1;return;} for(rt=2;;rt++){ bool w=1; int x=p-1; for(int i=2;i*i<=x;i++) if(x%i==0){ if(qpow(rt,(p-1)/i,p)==1){w=0;break;} while(x%i==0) x/=i; } if(x!=1 && qpow(rt,(p-1)/x,p)==1) w=0; if(w) break; }}void DFT(int *a){ for(int i=0;i
           
            =mod) a[j+k]-=mod; a[j+i+k]=x-y; if(x
            
             >1]>>1)|((i&1)<<(L-1)); while(T){ if(T&1) NTT(a,c); NTT(c,c); T>>=1; } for(int p=1,i=0;i