#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>n; mint inv2=mint(2).inv(); auto mul=[&](vectora,vectorb){ vectorres=ntt_convolution(a,b); reverse(all(b)); auto c=ntt_convolution(a,b); rep(i,c.size())res[abs(i+1-b.size())]+=c[i]; rep(i,res.size())res[i]*=inv2; debug(a,b,res); return res; }; auto dfs=[&](auto self,int n)->vector { if(n==0)return {1}; vectorc=self(self,n/2); auto res=mul(c,c); if(n&1)res=mul(res,{0,1}); return res; // vectorres=ntt_convolution(c,c); // auto d=c; // reverse(all(d)); // d=ntt_convolution(c,d); // rep(i,(int)c.size()-1,d.size()){ // res[i+1-c.size()]+=d[i]; // } // rep(i,res.size())res[i]*=inv2; // return res; //c*d[k]=i+(c.size()-1-j)==k i-j=k+1-c.size() }; auto ans=dfs(dfs,n); mint pow2=mint(2).pow(n); rep(i,ans.size())cout<