#include #include #include #include #include #include #include #include template constexpr std::enable_if_t<(std::numeric_limits::digits<=32),T>pow_mod(T a,T n,T mod){ using u64=unsigned long long; u64 res=1; while(n>0){ if(n&1)res=((u64)res*a)%mod; a=((u64)a*a)%mod; n>>=1; } return T(res); } template constexpr std::enable_if_t<(std::numeric_limits::digits>32),T>pow_mod(T a,T n,T mod){ using u128=__uint128_t; u128 res=1; while(n>0){ if(n&1)res=((u128)res*a)%mod; a=((u128)a*a)%mod; n>>=1; } return T(res); } constexpr int primitive_root_constexpr(int x){ if(x==167772161)return 3; if(x==469762049)return 3; if(x==754974721)return 11; if(x==880803841)return 26; if(x==998244353)return 3; if(x==2)return 1; int x2=x; int p[20]={}; int c=0; x--; for(int i=2;i*i<=x;i++){ if(x%i==0){ p[c++]=i; while(x%i==0)x/=i; } } if(x!=1)p[c++]=x; x=x2; for(int g=2;;g++){ bool ok=true; for(int i=0;i #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct ntt_root{ static constexpr int rank2=lsb(m-1); static constexpr int g=primitive_root_constexpr(m); std::arrayroot,invroot; std::arrayrate2,invrate2; std::arrayrate3,invrate3; constexpr ntt_root(){ root[rank2]=pow_mod(g,m>>rank2,m); invroot[rank2]=pow_mod(root[rank2],m-2,m); for(int i=rank2-1;i>=0;i--){ root[i]=(long long)root[i+1]*root[i+1]%m; invroot[i]=(long long)invroot[i+1]*invroot[i+1]%m; } int prod=1,invprod=1; for(int i=0;i void dft(std::vector&a){ static constexpr ntt_rootr; static constexpr unsigned long long mod2=(unsigned long long)T::mod()*T::mod(); int n=a.size(); int h=lsb(n); int len=0; while(len void idft(std::vector&a){ static constexpr ntt_rootr; int n=a.size(); int h=lsb(n); int len=h; while(len){ if(len==1){ int p=1<<(h-1); for(int i=0;i std::vectorntt_convolution(std::vector a,std::vector b){ int n=a.size(),m=b.size(),s=n+m-1; if(std::min(n,m)<60){ std::vectorret(s,0); if(nc(z); for(int i=0;i std::vector>convolution2d(const std::vector>&a,const std::vector>&b){ int x=a.size()+b.size()-1,y=a[0].size()+b[0].size()-1; std::vectorf(a.size()*y),g(b.size()*y); for(int i=0;i>ret(x,std::vector(y)); for(int i=0;i std::vector fps_inv(const std::vector &a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; const T zero=T::raw(0); assert(a[0]!=zero); std::vector ret(ceil_pow2(deg)); ret[0]=a[0].inv(); for(int m=1;m f(a.begin(),a.begin()+std::min(n,m*2)); if(f.size() g(ret); f.resize(m*2); dft(f); g.resize(m*2); dft(g); for(int i=0;i std::vector fps_diff(const std::vector&a){ int n=a.size(); std::vectorb(std::max(0,n-1)); for(int i=1;i std::vector fps_integral(const std::vector&a){ int n=a.size(); std::vectorb(n+1); b[0]=0; if(n)b[1]=1; for(int i=2;i<=n;i++)b[i]=-b[T::mod()%i]*(T::mod()/i); for(int i=0;i std::vector fps_log(const std::vector&a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; std::vectorb=fps_integral(ntt_convolution(fps_diff(a),fps_inv(a,deg))); return {b.begin(),b.begin()+deg}; } template std::vector fps_exp(const std::vector&a,int deg=-1){ assert(a.empty()||a[0]==0); int n=a.size(); if(deg==-1)deg=n; std::vectorinv(ceil_pow2(deg)); inv[0]=0,inv[1]=1; for(int i=2;ib{1,1y(b); y.resize(m*2); dft(y); f1=f2; std::vectorz(m); for(int i=0;ix(m); std::copy(a.begin(),a.begin()+std::min(n,m),x.begin()); for(int i=0;i=1;i--)x[i]=x[i-1]*inv[i]; x[0]=T(); for(int i=m;i std::vector fps_pow(std::vector a,unsigned long long k,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; if(k==0){ std::vectorret(deg,0); ret[0]=1; return ret; } int of=0; while(a[of]==0&&of!=n)of++; if(of==n)return std::vector(deg,0); if(of!=0&&k>=deg)return std::vector(deg,0); if(of*k>=deg)return std::vector(deg,0); a.erase(a.begin(),a.begin()+of); n=a.size(); T a0=a[0]; T inv=a[0].inv(); for(int i=0;ilg=fps_log(a,deg); T tk=T(k); for(int i=0;iep=fps_exp(lg,deg); T pw=a0.pow(k); for(int i=0;iret(deg,0); for(int i=of*k;i std::vectorfps_divmod(std::vectorf,std::vectorg){ if(f.empty())return f; int n=f.size(),m=g.size(); std::vectorr(f); std::reverse(f.begin(),f.end()),std::reverse(g.begin(),g.end()); std::vectorq=ntt_convolution(f,fps_inv(g,n)); q.resize(std::max(0,n-m+1)); auto p=ntt_convolution(g,q); std::reverse(p.begin(),p.end()); for(int i=0;i(p.size(),m);i++)r[i]-=p[i]; r.resize(m-1); while(!r.empty()&&r.back().val()==0)r.pop_back(); return r; } template std::optional>fps_sqrt(std::vectorf,int deg=-1){ if(deg==-1)deg=f.size(); int prefix_zero=0; while(prefix_zero(deg,0)); if(prefix_zero&1)return std::nullopt; f.erase(f.begin(),f.begin()+prefix_zero); prefix_zero/=2; auto opt_sq=f[0].sqrt(); if(!opt_sq)return std::nullopt; T sq=*opt_sq; T inv0=f[0].inv(); for(int i=0;ig{1}; T inv2=T::raw(2).inv(); while(g.size()fp(f.begin(),f.begin()+std::min(f.size(),g.size()*2)); fp=ntt_convolution(fp,fps_inv(g,g.size()*2)); std::vectornxtg(g); nxtg.resize(g.size()*2); for(int i=0;i void ntt_doubling(std::vector&a){ static constexpr ntt_rootr; int n=a.size()/2; std::vectorb(a.begin(),a.begin()+n); idft(b); T now=T::raw(n).inv(),zeta=T::raw(r.root[msb(n)+1]); for(int i=0;i std::vectorpower_prod_sum(std::vectorf,std::vectorg,int m){ assert(f.size()==g.size()); int s=f.size(); int n=ceil_pow2(f.size()),log2n=msb(n); for(int i=0;ilf(b*2),lg(b*2),rf(b*2),rg(b*2); int j; for(j=0;j+b=3)res=1<<(t-2); for(int i=3;i*i<=n;i++)if(n%i==0){ int c=0; while(n%i==0){ n/=i; c++; } int prod=i-1; for(int j=0;j struct mod_int{ private: static constexpr unsigned int umod=static_cast(m); static constexpr unsigned int car=carmichael_constexpr(m); using uint=unsigned int; using mint=mod_int; uint v; static_assert(mval()<=1)return *this; if constexpr(m%8==1){ mint b=2; while(b.pow((m-1)/2).val()==1)b++; int m2=m-1,e=0; while(m2%2==0)m2>>=1,e++; mint x=this->pow((m2-1)/2); mint y=(*this)*x*x; x*=*this; mint z=b.pow(m2); while(y.val()!=1){ int j=0; mint t=y; while(t.val()!=1)t*=t,j++; z=z.pow(1<<(e-j-1)); x*=z; z*=z; y*=z;e=j; } return x; } else if constexpr(m%8==5){ mint ret=this->pow((m+3)/8); if((ret*ret).val()==this->val())return ret; else return ret*mint::raw(2).pow((m-1)/4); } else{ return this->pow((m+1)/4); } } public: using value_type=uint; mod_int():v(0){} template,std::nullptr_t> =nullptr> mod_int(T a){ a%=m; if(a<0)v=a+umod; else v=a; } template,std::nullptr_t> =nullptr> mod_int(T a):v(a%umod){} static constexpr mint raw(int a){ mint ret; ret.v=a; return ret; } inline uint val()const{return this->v;} static constexpr int mod(){return m;} inline mint &operator+=(const mint &b){ this->v+=b.v; if(this->v>=umod)this->v-=umod; return *this; } inline mint &operator-=(const mint &b){ this->v-=b.v; if(this->v>=umod)this->v+=umod; return *this; } inline mint &operator*=(const mint &b){ this->v=((unsigned long long)this->v*b.v)%umod; return *this; } inline mint &operator/=(const mint &b){ *this*=b.inv(); return *this; } inline mint operator+()const{return *this;} inline mint operator-()const{return mint()-*this;} friend inline mint operator+(const mint &a,const mint &b){return mint(a)+=b;} friend inline mint operator-(const mint &a,const mint &b){return mint(a)-=b;} friend inline mint operator*(const mint &a,const mint &b){return mint(a)*=b;} friend inline mint operator/(const mint &a,const mint &b){return mint(a)/=b;} friend inline bool operator==(const mint &a,const mint &b){return a.val()==b.val();} friend inline bool operator!=(const mint &a,const mint &b){return !(a==b);} inline mint operator++(int){ mint ret=*this; *this+=mint::raw(1); return ret; } inline mint operator--(int){ mint ret=*this; *this-=mint::raw(1); return ret; } mint pow(long long n)const{ mint ret=mint::raw(1),a(*this); while(n){ if(n&1)ret*=a; a*=a; n>>=1; } return ret; } inline mint inv()const{ assert(this->v!=0); return pow(car-1); } std::optionalsqrt()const{ if(this->val()<=1||this->pow((m-1)/2)==1)return std::make_optional(this->sqrt_impl()); else return std::nullopt; } static constexpr unsigned int order(){return car;} friend std::istream &operator>>(std::istream &is,mint &b){ long long a; is>>a; b=mint(a); return is; } friend std::ostream &operator<<(std::ostream &os,const mint &b){ os< struct std::hash>{ std::size_t operator()(mod_intx)const{ return std::hash()(x.val()); } }; using mint998=mod_int<998244353>; using mint107=mod_int<1000000007>; using mint=mint998; using namespace std; int main(){ int n,m; cin>>n>>m; vectora(n),b(n); for(int i=0;i>b[i]; } a=power_prod_sum(a,b,m+1); for(int i=1;i<=m;i++)cout<