https://www.cnblogs.com/HocRiser/p/8207295.html 安利！

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define P 998244353#define N 550000char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,a[N],r[N],b[N],c[N],d[N],A[N],B[N],t;int ksm(int a,int k){ int s=1; for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P; return s;}int inv(int a){return ksm(a,P-2);}void DFT(int n,int *a,int g){ for (int i=0;i
           
            >1]>>1)|(i&1)*(n>>1); for (int i=0;i
            
             >1);k++,w=1ll*w*wn%P) { int x=a[k],y=1ll*w*a[k+(i>>1)]%P; a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P; } } }}void IDFT(int *a,int n){ DFT(n,a,inv(3)); int u=inv(n); for (int i=0;i
             
              >1); for (int i=0;i
              
               >=1; for (int i=n;i<(n<<1);i++) b[i]=0;}void trans(int *a,int *b,int n){for (int i=0;i
               
                >1); Inv(a,b,t>>1); mul(c,b,t); dx(c,a,t);}void Exp(int *a,int *b,int n) { if (n==1) {b[0]=1;return;} Exp(a,b,n>>1); for (int i=0;i<(n>>1);i++) B[i]=b[i]; for (int i=(n>>1);i