NTT(快速数论变换)用到的各种素数及原根：

 

NTT多项式乘法模板

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;const LL mod=998244353; //119*2^23+1   g=3const int N=(1<<19)+2;const int g=3;int rev[N];LL a[N],b[N];template
        
         void read(T &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }} LL Pow(LL a,LL b){    LL res=1;    for(;b;a=a*a%mod,b>>=1)        if(b&1) res=res*a%mod;    return res;}void NTT(LL *a,int n,int f){    for(int i=0;i
         
          >1]>>1)|((i&1)<