#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL clock_t start=clock(); #endif int testcase=1; //cin>>testcase; for(int i=0;i struct ntt_root{ static constexpr int rank2=countr_zero(T::mod()-1); int g=primitive_root(T::mod()); arrayroot,invroot; arrayrate2,invrate2; arrayrate3,invrate3; ntt_root(){ root[rank2]=T::raw(g).pow((T::mod())>>rank2); invroot[rank2]=root[rank2].inv(); for(int i=rank2-1;i>=0;i--){ root[i]=root[i+1]*root[i+1]; invroot[i]=invroot[i+1]*invroot[i+1]; } { T prod=1,invprod=1; rep(i,rank2-1){ rate2[i]=root[i+2]*prod; invrate2[i]=invroot[i+2]*invprod; prod*=invroot[i+2]; invprod*=root[i+2]; } } { T prod=1,invprod=1; rep(i,rank2-2){ rate3[i]=root[i+3]*prod; invrate3[i]=invroot[i+3]*invprod; prod*=invroot[i+3]; invprod*=root[i+3]; } } } }; template void dft(vector&a){ int n=a.size(); static const ntt_root r; int h=countr_zero(n); ull mod2=(ull)T::mod()*T::mod(); int len=0; while(len void idft(vector&a){ int n=a.size(); static const ntt_root r; int h=countr_zero(n); ull mod2=(ull)T::mod()*T::mod(); int len=h; while(len){ if(len==1){ int p=1<<(h-1); T rot=1; rep(i,p){ T u=a[i],v=a[i+p]; a[i]=u+v; a[i+p]=(ull)(u.val()-v.val()+T::mod())*rot.val(); } len--; } else{ int p=1<<(h-len); T rot=1,imag=r.invroot[2]; rep(s,1<<(len-2)){ T rot2=rot*rot,rot3=rot*rot2; int of=s<<(h-len+2); rep(i,p){ ull a0=a[i+of].val(),a1=a[i+of+p].val(),a2=a[i+of+p*2].val(),a3=a[i+of+p*3].val(); ull k=T((T::mod()+a2-a3)*imag.val()).val(); a[i+of]=a0+a1+a2+a3; a[i+of+p]=(a0+T::mod()-a1+k)*rot.val(); a[i+of+p*2]=(a0+a1+T::mod()*2-a2-a3)*rot2.val(); a[i+of+p*3]=(a0+T::mod()*2-a1-k)*rot3.val(); } if(s+1!=1<<(len-2))rot*=r.invrate3[countr_zero(~(unsigned int)s)]; } len-=2; } } } template vectorntt_convolution(vector a,vector b){ int n=a.size(),m=b.size(),s=n+m-1; if(min(n,m)<60){ vectorret(s,0); if(nc(z); rep(i,z)c[i]=a[i]*b[i]; idft(c); T g=T::raw(z).inv(); rep(i,s)c[i]*=g; return {c.begin(),c.begin()+s}; } template vector fps_inv(const vector &a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; assert(a[0]!=T(0)); vector ret(deg); ret[0]=a[0].inv(); for(int m=1;m f(a.begin(),a.begin()+min(n,m*2)); if(f.size() g(ret); f.resize(m*2); dft(f); g.resize(m*2); dft(g); rep(i,m*2)f[i]*=g[i]; idft(f); T inv=T::raw(m*2).inv(); rep(i,m)f[i]=0; reps(i,m,m*2)f[i]*=inv; dft(f); rep(i,m*2)f[i]*=g[i]; idft(f); rep(i,m*2)f[i]*=inv; reps(i,m,min(deg,m*2))ret[i]-=f[i]; } return ret; } template vector fps_diff(const vector&a){ int n=a.size(); vectorb(max(0,n-1)); reps(i,1,n)b[i-1]=a[i]*i; return b; } template vector fps_integral(const vector&a){ int n=a.size(); vectorb(n+1); b[0]=0; if(n)b[1]=1; reps(i,2,n+1)b[i]=-b[T::mod()%i]*(T::mod()/i); rep(i,n)b[i+1]*=a[i]; return b; } template vector fps_log(const vector&a,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; vectorb=fps_integral(ntt_convolution(fps_diff(a),fps_inv(a,deg))); return {b.begin(),b.begin()+deg}; } template vector fps_exp(const vector&a,int deg=-1){ assert(a.empty()||a[0]==0); int n=a.size(); if(deg==-1)deg=n; vectorb{1}; for(int m=1;mnxt=fps_log(b,m*2); rep(i,m*2)nxt[i]*=-1; rep(i,min(n,m*2))nxt[i]+=a[i]; nxt[0]++; b=ntt_convolution(b,nxt); b.resize(m*2); } return {b.begin(),b.begin()+deg}; } template vector fps_pow(vector a,ll k,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; if(k==0){ vectorret(deg,0); ret[0]=1; return ret; } int of=0; while(a[of]==0&&of!=n)of++; if(of==n)return vector(deg,0); if(of!=0&&k>=deg)return vector(deg,0); if(of*k>=deg)return vector(deg,0); a.erase(a.begin(),a.begin()+of); n=a.size(); T a0=a[0]; T inv=a[0].inv(); rep(i,n)a[i]*=inv; vectorlg=fps_log(a,deg); rep(i,deg)lg[i]*=k; vectorep=fps_exp(lg,deg); T pw=a0.pow(k); rep(i,deg)ep[i]*=pw; vectorret(deg,0); reps(i,of*k,deg)ret[i]=ep[i-of*k]; return ret; } template vector fps_pow_sparse(const vector&a,ll k,int deg=-1){ int n=a.size(); if(deg==-1)deg=n; vector>b; rep(i,n)if(a[i]!=0)b.emplace_back(i,a[i]); if(b.empty()){ vectorret(deg,0); if(k==0)ret[0]=1; return ret; } int of=b[0].first; T b0=b[0].second,inv=b0.inv(); for(auto &i:b){ i.first-=of; i.second*=inv; } b0=b0.pow(k); vectorret(deg,0); ret[0]=1; rep(i,deg-1){ T cu=0; for(auto [j,c]:b){ if(i-j+1<0)continue; if(j==0)continue; cu-=c*ret[i-j+1]*(i-j+1); cu+=ret[i-j+1]*k*j*c; } ret[i+1]=cu/(i+1); } if(of){ if(k>=deg||of*k>=deg)ret.assign(deg,0); else{ ret.insert(ret.begin(),of*k,0); ret.resize(deg); } } for(auto &i:ret)i*=b0; return ret; } template vector fps_div_sparse(vector a,const vector&b,int deg=-1){ int n=a.size(),m=b.size(); if(deg==-1)deg=n; a.resize(deg,0); assert(b[0]!=0); vector>c; reps(i,1,m)if(b[i]!=0)c.emplace_back(i,b[i]); T v=b[0].inv(); rep(i,deg){ for(auto [j,e]:c){ if(j>i)break; a[i]-=a[i-j]*e; } a[i]*=v; } return a; } template inline vector fps_inv_sparse(const vector&a,int deg=-1){ return fps_div_sparse({1},a,(deg==-1?a.size():deg)); } template vectorfps_fode_sparse(const vector&a,const vector&b){ assert(a.size()==b.size()); assert(a[0]==1); int n=a.size(); vector>c,d; reps(i,1,n)if(a[i]!=0)c.emplace_back(i,a[i]); rep(i,n)if(b[i]!=0)d.emplace_back(i,b[i]); vectorf(n),df(n-1); f[0]=1; vectorinv(n); rep(i,n-1){ T v=0; for(auto [j,x]:c){ if(j>i)break; v+=x*df[i-j]; } for(auto [j,x]:d){ if(j>i)break; v+=x*f[i-j]; } df[i]=-v; if(i==0)inv[1]=1; else inv[i+1]=-inv[T::mod()%(i+1)]*(T::mod()/(i+1)); f[i+1]=df[i]*inv[i+1]; } return f; } template vector fps_pow_sparse(const vector&a,const vector&b,ll k,ll l,int deg=-1){ int n=a.size(),m=b.size(); if(deg==-1)deg=n; assert(a[0]==1); vector>c,d; rep(i,n)if(a[i]!=0)c.emplace_back(i,a[i]); rep(i,m)if(b[i]!=0)d.emplace_back(i,b[i]); vectorf(deg,0),g(deg,0); for(auto [i,x]:c){ for(auto [j,y]:d){ if(i+j>=deg+1)continue; T z=x*y; if(i+j T bostan_mori(vector p,vector q,ll k){ int z=1; int n=p.size(),m=q.size(); while(zv(z/2); rep(i,z/2)v[i]=q[i*2]*q[i*2+1]; idft(p),idft(v); T inv=T::raw(z).inv(),inv2=inv*2; rep(i,z/2)v[i]*=inv2; vectoru(n); if(k&1)rep(i,n)u[i]=p[i*2+1]*inv; else rep(i,n)u[i]=p[i*2]*inv; u.resize(z,0),v.resize(z,0); swap(p,u),swap(q,v); k>>=1; } return p[0]; } template vector berlekamp_massey(const vector&s){ const int n=s.size(); vectorb,c; b.reserve(n+1),c.reserve(n+1); b.emplace_back(1),c.emplace_back(1); T y=1; reps(i,1,n+1){ int l=c.size(),m=b.size(); T x=0; rep(j,l)x+=c[j]*s[i-l+j]; b.emplace_back(0); ++m; if(x==0)continue; T f=x/y; if(l T kth_term(vectorp,ll k){ vectorq=berlekamp_massey(p); if(T::mod()==998244353){ p=ntt_convolution(p,q); p.resize(q.size()-1); return bostan_mori(p,q,k); } auto convolution_naive=[](vector&x,const vector&y)->void { vectortemp(x.size()+y.size()-1,0); rep(i,x.size())rep(j,y.size())temp[i+j]+=x[i]*y[j]; swap(x,temp); }; convolution_naive(p,q); int n=q.size(); p.resize(n-1); vectormq(n); while(k){ rep(i,n)mq[i]=q[i]*(i&1?-1:1); convolution_naive(p,mq); convolution_naive(q,mq); vectoru(n-1),v(n); if(k&1)rep(i,n-1)u[i]=p[i*2+1]; else rep(i,n-1)u[i]=p[i*2]; rep(i,n)v[i]=q[i*2]; swap(p,u),swap(q,v); k>>=1; } if(p.empty())return 0; else return p[0]; } template struct factorial_table{ private: int mod,capacity; vectorfact,factinv,inv; void resize(int n){ fact.resize(n+1),factinv.resize(n+1),inv.resize(n+1); for(int i=capacity+1;i<=n;i++){ fact[i]=fact[i-1]*i; inv[i]=-inv[mod%i]*(mod/i); factinv[i]=factinv[i-1]*inv[i]; } capacity=n; } public: factorial_table():capacity(1),mod(T::mod()),fact{1,1},factinv{1,1},inv{0,1}{} T C(int n,int k){ if(n T O(INT...k){ int n=0; for(int i:initializer_list{k...}){ if(i<0)return 0; n+=i; } if(capacity{k...})ret*=factinv[i]; return ret; } }; using mint=modint998244353; factorial_table table; void SOLVE(){ int n,k; cin>>n>>k; vectorf,g,h; //f*g=h g.resize(k+1); rep(i,k+1)g[i]=table.fact_inv(i); h.resize(k+1); rep(i,k+1)h[i]=table.fact_inv(i)*mint(i).pow(n); f=ntt_convolution(fps_inv(g),h); f.resize(k+1); vectore(k+1); for(int i=1;i