#include using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; 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,tuple&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;} templateistream &operator>>(istream &is,array&a){for(auto&i:a)is>>i;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 overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} 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; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i #include constexpr int carmichael_constexpr(int n){ if(n==998244353)return 998244352; if(n==1000000007)return 1000000006; if(n<=1)return n; int res=1; int t=0; while(n%2==0){ n/=2; t++; } if(t==2)res=2; else if(t>=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>; 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 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 struct SemiRelaxedConvolution{ private: std::vectorf,g,h; std::vector>f_memo,g_memo; int p,n,loglog2n,na; std::vectortemp; static constexpr int b=4; static constexpr int d=6; static_assert(b<=d); static_assert((unsigned long long)(T::mod()-1)*(T::mod()-1)<=(-1ull)/(1<&f_):f(f_),p(0){ n=ceil_pow2(f.size()+1)-1; f.resize(n),g.resize(n),h.resize(n); temp.resize(n); loglog2n=[&]()->int { int n2=n+1; int res=0; while(n2>(1<>=b; } return res; }(); f_memo.resize(loglog2n),g_memo.resize(loglog2n); na=msb(n+1)-loglog2n*b; for(int i=0,sq=(n+1)>>(loglog2n*b);i&c=f_memo[i]; c.resize((n/sq)*sq*2); g_memo[i].resize(c.size()); std::vectorbuf(sq*2); for(int j=0;j+sq*2-1<=n;j+=sq){ std::copy(f.begin()+j,f.begin()+j+sq*2-1,buf.begin()); buf[sq*2-1]=T(); dft(buf); std::copy(buf.begin(),buf.end(),c.begin()+j*2); } } } T query(T v){ g[p]=v; int p2=p+1; int w=lsb(p2); if(w>((loglog2n-w)*b); int lc=(p2>>(na+w*b))&((1<buf(sq*2); std::copy(g.begin()+p2-sq,g.begin()+p2,buf.begin()); dft(buf); std::copy(buf.begin(),buf.end(),g_memo[w].begin()+(p2-sq)*2); for(int i=0;i struct is_modint_impl{ template static auto check(T&&x)->decltype(x.mod(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct is_modint:public decltype(is_modint_impl::check(std::declval())){}; template inline constexpr bool is_modint_v=is_modint::value; struct is_dynamic_modint_impl{ template static auto check(T&&x)->decltype(x.set_mod((typename T::value_type)0),std::true_type{}); template static auto check(...)->std::false_type; }; template struct is_dynamic_modint:public decltype(is_dynamic_modint_impl::check(std::declval())){}; template inline constexpr bool is_dynamic_modint_v=is_dynamic_modint::value; template inline constexpr bool is_static_modint_v=is_modint_v&&!is_dynamic_modint_v; struct is_uso_modint_impl{ template static auto check(T&&x)->decltype(x.uso(),std::true_type{}); template static auto check(...)->std::false_type; }; template struct is_uso_modint:public decltype(is_uso_modint_impl::check(std::declval())){}; template inline constexpr bool is_uso_modint_v=is_uso_modint::value; template struct F{ private: static int capacity; static std::vectorfact,factinv,inv; public: static void resize(int n){ if(capacity>=n)return; 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]*T::raw(i); if constexpr(is_uso_modint_v)inv[i]=T(1)/T(i); else inv[i]=-inv[T::mod()%i]*(T::mod()/i); factinv[i]=factinv[i-1]*inv[i]; } capacity=n; } static T C(int n,int k){ if(n static T O(INT...k){ int n=0; for(int i:std::initializer_list{k...}){ if(i<0)return 0; n+=i; } resize(n); T ret=fact[n]; for(int i:std::initializer_list{k...})ret*=factinv[i]; return ret; } }; templateint F::capacity=1; templatestd::vectorF::fact{1,1}; templatestd::vectorF::factinv{1,1}; templatestd::vectorF::inv{0,1}; using mint=mint998; void SOLVE(){ int n; cin>>n; vectordp(n+2); dp[n]=1; vectorpow2(n+1),pow3(n+1); pow2[0]=pow3[0]=1; rep(i,1,n+1)pow2[i]=pow2[i-1]*mint::raw(2),pow3[i]=pow3[i-1]*mint::raw(3); vectorpow2j23inv(n+1); rep(i,2,n+1)pow2j23inv[i]=((pow2[i]-mint::raw(2))*mint::raw(3)).inv(); for(int i=n-1;i>=1;i--){ rep(j,i+1,n+1){ dp[i]+=dp[j]*F::C(j,i)*mint::raw(3)*pow2j23inv[j]; } } rep(i,2,n+1)dp[i]*=pow3[i]*pow2j23inv[i]; for(int i=n-1;i>=1;i--)dp[i]+=dp[i+1]; rep(i,1,n+1)cout<