#pragma once
#include <bits/stdc++.h>
usingnamespacestd;#include "./mint.cpp"
// NumberTheoreticTransform supports only F_998244353 as coefficient.// recursive versionstructNumberTheoreticTransform{private:constmintROOT=3;constintMOD=998244353;public:NumberTheoreticTransform(){}// ntt calculates y[i] = \sum_{j=0}^{n-1} x[j]r^{ij} where n is length of x and r is n-th root of 1 (mod n)// n must be power of two (n = 2^m)voidntt(intm,mintnth_root,std::vector<mint>&x){if(m==0)return;intn=(int)x.size();assert(n==(1<<m));intn_half=n/2;std::vector<mint>x_e(n_half),x_o(n_half);for(inti=0;i<n_half;i++){x_e[i]=x[i<<1];x_o[i]=x[i<<1|1];}ntt(m-1,nth_root*nth_root,x_e);ntt(m-1,nth_root*nth_root,x_o);mintroot_pow=1;intmask=n_half-1;for(inti=0;i<n;i++){x[i]=x_e[i&mask]+root_pow*x_o[i&mask];root_pow*=nth_root;}}// multiply calculates f*g, when f[i] is coefficients of x^i (0-indexed) and g[i] is coefficients of x^i (0-indexed)std::vector<mint>multiply(std::vector<mint>f,std::vector<mint>g){intmin_sz=(int)f.size()+(int)g.size()+1;intm=0;while((1<<m)<min_sz){++m;}intsz=1<<m;f.resize(sz,(mint)0);g.resize(sz,(mint)0);assert((MOD-1)%sz==0);constmintnth_root=ROOT.pow((longlong)(MOD-1)/sz);ntt(m,nth_root,f);ntt(m,nth_root,g);std::vector<mint>h(sz);for(inti=0;i<sz;i++){h[i]=f[i]*g[i];}ntt(m,nth_root.inverse(),h);mintn_inv=mint(sz).inverse();for(inti=0;i<sz;i++){h[i]*=n_inv;}returnh;}};
#line 2 "math/number_theoretic_transform.cpp"
#include <bits/stdc++.h>
usingnamespacestd;#line 3 "math/mint.cpp"
usingnamespacestd;template<intMOD>structModInt{public:longlongx;ModInt(longlongx=0):x((x%MOD+MOD)%MOD){}constexprModInt&operator+=(constModInta)noexcept{if((x+=a.x)>=MOD)x-=MOD;return*this;}constexprModInt&operator-=(constModInta)noexcept{if((x+=MOD-a.x)>=MOD)x-=MOD;return*this;}constexprModInt&operator*=(constModInta)noexcept{(x*=a.x)%=MOD;return*this;}constexprModInt&operator/=(constModInta)noexcept{return*this*=a.inverse();}constexprModIntoperator+(constModInta)constnoexcept{returnModInt(*this)+=a.x;}constexprModIntoperator-(constModInta)constnoexcept{returnModInt(*this)-=a.x;}constexprModIntoperator*(constModInta)constnoexcept{returnModInt(*this)*=a.x;}constexprModIntoperator/(constModInta)constnoexcept{returnModInt(*this)/=a.x;}friendconstexprstd::ostream&operator<<(std::ostream&os,constModInt<MOD>a)noexcept{returnos<<a.x;}friendconstexprstd::istream&operator>>(std::istream&is,ModInt<MOD>&a)noexcept{is>>a.x;a.x=(a.x%MOD+MOD)%MOD;returnis;}ModIntinverse()constnoexcept{// x ^ (-1)longlonga=x,b=MOD,p=1,q=0;while(b){longlongd=a/b;a-=d*b;swap(a,b);p-=d*q;swap(p,q);}returnModInt(p);}ModIntpow(longlongN)constnoexcept{// x ^ NModInta=1;ModInty=this->x;while(N){if(N&1)a*=y;y*=y;N>>=1;}returna;}};template<typenameU,intMOD>inlineModInt<MOD>operator*(constU&c,constModInt<MOD>&a){return{c*a.x};}usingmint=ModInt<998244353>;#line 5 "math/number_theoretic_transform.cpp"
// NumberTheoreticTransform supports only F_998244353 as coefficient.// recursive versionstructNumberTheoreticTransform{private:constmintROOT=3;constintMOD=998244353;public:NumberTheoreticTransform(){}// ntt calculates y[i] = \sum_{j=0}^{n-1} x[j]r^{ij} where n is length of x and r is n-th root of 1 (mod n)// n must be power of two (n = 2^m)voidntt(intm,mintnth_root,std::vector<mint>&x){if(m==0)return;intn=(int)x.size();assert(n==(1<<m));intn_half=n/2;std::vector<mint>x_e(n_half),x_o(n_half);for(inti=0;i<n_half;i++){x_e[i]=x[i<<1];x_o[i]=x[i<<1|1];}ntt(m-1,nth_root*nth_root,x_e);ntt(m-1,nth_root*nth_root,x_o);mintroot_pow=1;intmask=n_half-1;for(inti=0;i<n;i++){x[i]=x_e[i&mask]+root_pow*x_o[i&mask];root_pow*=nth_root;}}// multiply calculates f*g, when f[i] is coefficients of x^i (0-indexed) and g[i] is coefficients of x^i (0-indexed)std::vector<mint>multiply(std::vector<mint>f,std::vector<mint>g){intmin_sz=(int)f.size()+(int)g.size()+1;intm=0;while((1<<m)<min_sz){++m;}intsz=1<<m;f.resize(sz,(mint)0);g.resize(sz,(mint)0);assert((MOD-1)%sz==0);constmintnth_root=ROOT.pow((longlong)(MOD-1)/sz);ntt(m,nth_root,f);ntt(m,nth_root,g);std::vector<mint>h(sz);for(inti=0;i<sz;i++){h[i]=f[i]*g[i];}ntt(m,nth_root.inverse(),h);mintn_inv=mint(sz).inverse();for(inti=0;i<sz;i++){h[i]*=n_inv;}returnh;}};