「集训队作业2020」春天，在积雪下结一成形，抽枝发芽

#include<bits/stdc++.h>
namespace mem{ //v2.10.1 => size: 15.80KiB
  #ifdef memset0
  #else
    #define MEM_FASTIO
  #endif

  #ifdef __SIZEOF_INT128__
    #define MEM_INT128
  #endif

  #define __integer_mapper(func)    \
      func(int)                     \
      func(unsigned int)            \
      func(long long int)           \
      func(unsigned long long int)
  #define __float_mapper(func)        \
      func(float)                     \
      func(double)                    \
      func(long double)
  
  namespace stdval{
    using i32=int;
    using i64=long long;
    using u32=unsigned;
    using u64=unsigned long long;
    using f32=float;
    using f64=double;
    using f96=long double;
  #ifdef MEM_INT128
    using i128=__int128_t;
    using u128=__uint128_t;
  #endif
  }
  
  namespace utils{
    using std::cin;
    using std::tie;
    using std::get;
    using std::cout;
    using std::cerr;
    using std::endl;
    using std::swap;
    using std::sort;
    using std::find;
    using std::copy;
    using std::fill;
    using std::unique;
    using std::reverse;
    using std::shuffle;
    using std::function;
    using std::make_pair;
    using std::make_tuple;
    using std::accumulate;
    using std::lower_bound;
    using std::upper_bound;
    using std::max_element;
    using std::min_element;
    using std::next_permutation;
  }
  
  namespace random{
    const int LuckyNumber=0726; // Kanbe Kotori's Birthday
    std::mt19937 rng(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
    std::mt19937_64 rng64(LuckyNumber^std::chrono::steady_clock::now().time_since_epoch().count());
    
    template<class T> inline T rand(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
    template<class T> inline T rand64(T l,T r){return std::uniform_int_distribution<T>(l,r)(rng);}
  }
  
  namespace modint{
    template<const int mod> struct Z{
      int x;
      inline Z(){x=0;}
      inline Z(int t){x=t;}
      inline Z(long long t){x=t%mod,x<0&&(x+=mod);}
      
      inline void operator-=(Z a){(x-=a.x)<0&&(x+=mod);}
      inline void operator+=(Z a){(x+=a.x)>=mod&&(x-=mod);}
      inline void operator*=(Z a){x=(long long)x*a.x%mod;}
      
      friend inline Z operator*(Z a,Z b){return (long long)a.x*b.x%mod;}
      friend inline Z operator-(Z a,Z b){return ((a.x-=b.x)<0&&(a.x+=mod)),a;}
      friend inline Z operator+(Z a,Z b){return ((a.x+=b.x)>=mod&&(a.x-=mod)),a;}
    };
    
    template<const int mod> inline Z<mod> finv(Z<mod> x){
      if(x.x<2)return x;
      return (mod-mod/x.x)*finv(mod%x.x);
    }
    template<const int mod> inline Z<mod> fpow(Z<mod> a,int b){
      Z<mod> s=1;
      for(;b;b>>=1,a=a*a)
        if(b&1)s=s*a;
      return s;
    }
    
    template<const int mod> inline void init_inverse(int n,Z<mod> *inv){
      inv[0]=inv[1]=1;
      for(int i=2;i<n;i++)inv[i]=(mod-mod/i)*inv[mod%i];
    }
    template<const int mod> inline void init_factorial(int n,Z<mod> *fac,Z<mod> *ifac){
      fac[0]=1,init_inverse(n,ifac);
      for(int i=1;i<n;i++)fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*ifac[i];
    }
  }
  
  namespace math{
    using namespace stdval;
    using std::max;
    using std::min;
    template<class T> inline T abs(T x){return x<0?-x:x;}
    template<class T> inline T gcd(T n,T m){return m?gcd(m,n%m):n;}
    template<class T> inline T lcm(T n,T m){return n/gcd(n,m)*m;}
    
    struct FastDiv{
      u64 t,i;
      inline FastDiv(u64 p):t(u64(-1)/p),i(mul_inv(p)){}
      
      inline bool divide(u64 n){return n*i<=t;}
      inline bool divide(i64 n){return u64(n<0?-n:n)*i<=t;}
      inline u64 mul_inv(u64 n){
        u64 x=n;
        for(int i=0;i<5;++i)x*=2-n*x;
        return x;
      }
    };
  
  #ifdef MEM_INT128
    struct FastMod{
      u64 m,b;
      inline FastMod(u64 b):m(u64((u128(1)<<64)/b)),b(b){}
      
      inline u64 reduce(u64 a){
        u64 q=(u64)((u128(m)*a)>>64);
        u64 r=a-q*b;
        return r>=b?r-b:r;
      }
    };
  #endif
  }
  
  namespace container{
    using std::pair;
    using std::tuple;
    using std::set;
    using std::multiset;
    using std::unordered_set;
    using std::unordered_multiset;
    using std::map;
    using std::multimap;
    using std::unordered_map;
    using std::unordered_multimap;
    using std::queue;
    using std::stack;
    using std::priority_queue;
    using std::deque;
    using std::bitset;
    
    using std::tie;
    using std::get;
    using std::make_pair;
    using std::make_tuple;
    
    template<class T> struct vector:std::vector<T>{
      using std::vector<T>::vector;
      using iterator=typename std::vector<T>::iterator;
      using const_iterator=typename std::vector<T>::const_iterator;
      vector():std::vector<T>(){}
      explicit vector(const std::vector<T> &plain):std::vector<T>(plain){}
      
      inline void reverse(){std::reverse(this->begin(),this->end());}
      inline void unique(){this->erase(std::unique(this->begin(),this->end()),this->end());}
      inline void concat(const vector &rhs){this->insert(this->end(),rhs.begin(),rhs.end());}
      inline bool includes(const T &x) const{return std::find(this->begin(),this->end(),x)!=this->end();}
      template<class Function> inline void forEach(Function func){for(const auto &it:*this)func(it);}
      
      inline iterator find(const T &x){return std::find(this->begin(),this->end(),x);}
      inline iterator lower_bound(const T &x){return std::lower_bound(this->begin(),this->end(),x);}
      inline iterator upper_bound(const T &x){return std::upper_bound(this->begin(),this->end(),x);}
      inline const_iterator find(const T &x)const{return std::find(this->begin(),this->end(),x);}
      inline const_iterator lower_bound(const T &x)const{return std::lower_bound(this->begin(),this->end(),x);}
      inline const_iterator upper_bound(const T &x)const{return std::upper_bound(this->begin(),this->end(),x);}

      inline void sort(){std::sort(this->begin(),this->end());}
      template<class Function> inline void sort(Function func){std::sort(this->begin(),this->end(),func);}
      
      inline vector slice(int l,int r) const{
        if(l>r)return {};
        if(r<this->size())return vector(this->begin()+l,this->begin()+r);
        vector rsp(this->begin()+l,this->end());
        return rsp.resize(r-l),rsp;
      }

      inline void from(const std::set<T> &src){
        this->resize(src.size());
        auto it=this->begin();
        for(const T e:src)*it++=e;
      }

      template<class R,class Function> inline vector<R> _map(Function func) const{
        vector<R> res(this->size());
        for(size_t i=0;i<this->size();i++)
          res[i]=func(this->operator[](i));
        return res;
      }
      template<class R> inline vector<R> map(R func(T)) const{return this->_map<R>(func);}
      template<class R> inline vector<R> map(const std::function<R(T)> &func) const{return this->_map<R>(func);}
    };
    
    struct string:std::string{
      using std::string::string;
      string():std::string(""){}
      string(const std::string &plain):std::string(plain){}
      
      template<class T> inline string join(const vector<T> &vet) const;
            
      inline string slice(int l,int r) const{
        if(l>r)return {};
        if(r<this->size())return string(this->begin()+l,this->begin()+r);
        string rsp(this->begin()+l,this->end());
        return rsp.resize(r-l),rsp;
      }
      
      vector<string> split(const string &dim) const{
        if(this->empty())return {};
        char *src=new char[this->length()+1];
        strcpy(src,this->c_str());
        char *tar=new char[dim.length()+1];
        strcpy(tar,dim.c_str());
        vector<string> rsp;
        for(char *pos=strtok(src,tar);pos;pos=strtok(nullptr,tar))
          rsp.push_back(string(pos));
        delete[] src;
        delete[] tar;
        return rsp;
      }
      
      template<class... Args> static inline string format(const char *fm,Args... args){
        int len=snprintf(nullptr,0,fm,args...);
        char *buf=new char[len+1];
        snprintf(buf,len+1,fm,args...);
        string str(buf);
        delete[] buf;
        return str;
      }
      template<class... Args> static inline string format(const string &fm,Args... args){
        return format(fm.c_str(),args...);
      }
    };
  
  #define __to_string(T)                   \
      inline string to_string(const T &x){ \
        return std::to_string(x);          \
      }
    __float_mapper(__to_string)
    __integer_mapper(__to_string)
  #undef __to_string
    
    inline string to_string(const string &s){return s;}
    inline string to_string(const char *s){return string(s);}
    inline string to_string(const std::string &s){return string(s);}
    template<const int mod> inline string to_string(const modint::Z<mod> &v){return std::to_string(v.x);}
    
    template<class T> inline string to_string(const vector<T> &ctn){return "["+string(",").join(ctn)+"]";}
    template<class T> inline string to_string(const set<T> &ctn){
      string result="{";
      bool flag=false;
      for(const auto &it:ctn){
        if(flag)result+=",";
        flag=true;
        result+=to_string(it);
      }
      return result+"}";
    }
    template<class T1,class T2> inline string to_string(const map<T1,T2> &ctn){
      string result="{";
      bool flag=false;
      for(const auto &it:ctn){
        if(flag)result+=",";
        flag=true;
        result+=to_string(it.first)+":"+to_string(it.second);
      }
      return result+"}";
    }
    
    template<class T> inline string string::join(const vector<T> &vet) const{
      if(!vet.size())return "";
      string res=to_string(vet[0]);
      for(size_t i=1;i<vet.size();i++){
        res+=*this;
        res+=to_string(vet[i]);
      }
      return res;
    }
    
    inline string operator "" _s(const char *s){return string(s);}
    inline string operator "" _s(const char *s,size_t len){return string(s,len);}
    inline string operator "" _s(long double x){return to_string(x);}
    inline string operator "" _s(unsigned long long int x){return to_string(x);}
  }
  
  namespace io{
  #ifdef MEM_FASTIO
    namespace fastio{
      const int BUFFER=1<<18;
      char ibuf[BUFFER],*iS,*iT;
      inline int getc(){
        if(iS==iT){
          iT=(iS=ibuf)+fread(ibuf,1,BUFFER,stdin);
          return iS==iT?EOF:*iS++;
        }else{
          return *iS++;
        }
      }
      char obuf[BUFFER],*oS=obuf,*oT=oS+BUFFER-1;
      inline void flush(){
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
      }
      inline void putc(int x){
        *oS++=x;
        if(oS==oT)flush();
      }
      struct Flusher{~Flusher(){flush();}}flusher;
    }
    using fastio::getc;
    using fastio::putc;
    inline void flush(){fastio::flush(),fflush(stdout);}
  #else
    inline int getc(){return getchar();}
    inline void putc(int c){putchar(c);}
    inline void flush(){fflush(stdout);}
  #endif
    
    template<class T> inline void read_digit(T &x){x=getc(); while(!isdigit(x))x=getc();}
    template<class T> inline void read_alpha(T &x){x=getc(); while(!isalpha(x))x=getc();}
    template<class T> inline void read_lower(T &x){x=getc(); while(!islower(x))x=getc();}
    template<class T> inline void read_upper(T &x){x=getc(); while(!isupper(x))x=getc();}
    inline int read_digit(){int x; read_digit(x); return x;}
    inline int read_alpha(){int x; read_alpha(x); return x;}
    inline int read_lower(){int x; read_lower(x); return x;}
    inline int read_upper(){int x; read_upper(x); return x;}
  
  #define __read(T)                             \
      inline void read(T &x) {                  \
        x=0; bool f=0; char c=getc();           \
        while(!isdigit(c))f^=c=='-',c=getc();   \
        while(isdigit(c))x=x*10+c-'0',c=getc(); \
        if(f)x=-x;                              \
      }
    __integer_mapper(__read)
    #ifdef MEM_INT128
      __read(__int128_t)
      __read(__uint128_t)
    #endif
  #undef __read
    
    inline void read(char &x){x=getc();}
    inline void read(char *s){
      char c=getc();
      while(~c&&!isspace(c))*s++=c,c=getc();
      *s++='\0';
    }
    inline void read(container::string &s){
      char c=getc();
      s="";
      while(~c&&!isspace(c))s+=c,c=getc();
    }
    template<const int mod> inline void read(const modint::Z<mod> &x){read(x.x);}
    
    template<class T=int> inline T read(){T x; read(x); return x;}
    template<class T,class... Args> inline void read(T &x,Args &... args){
      read(x),read(args...);
    }
  
  #define __print(T)           \
      inline void print(T x){  \
        if(x<0)putc('-'),x=-x; \
        if(x>9)print(x/10);    \
        putc('0'+x%10);        \
      }
    __integer_mapper(__print)
    #ifdef MEM_INT128
      __print(__int128_t)
      __print(__uint128_t)
    #endif
  #undef __print
    
    inline void print(char x){putc(x);}
    inline void print(const char *s){
      size_t len=strlen(s);
      for(size_t i=0;i<len;i++)putc(s[i]);
    }
    inline void print(const container::string &s){
      for(size_t i=0;i<s.length();i++)putc(s[i]);
    }
    template<const int mod> inline void print(const modint::Z<mod> &x){print(x.x);}
    
    template<class T,class... Args> inline void print(const T &x,Args... args){
      print(x),print(args...);
    }
    template<class... Args> inline void println(Args... args){
      print(args...),putc('\n');
    }
    
    template<class... Args> inline void printfm(const char *formatter,Args... arguments){
      print(container::string().format(formatter,arguments...));
    }
    template<class... Args> inline void printfm(const container::string &formatter,Args... arguments){
      print(container::string().format(formatter,arguments...));
    }
  }
  
  namespace logger{
    enum ConsoleColor{
      NOPE=-1,BLACK,RED,GREEN,YELLOW,BLUE,PURPLE,DEEPBLUE
    };
    template<const ConsoleColor color=NOPE,class... Args> inline void log(const char *formatter,Args... args){
  #ifdef memset0
      if(~color){
        fprintf(stderr,"\033[%dm",30+color);
        fprintf(stderr,formatter,args...);
        fprintf(stderr,"\033[0m");
      }else{
        fprintf(stderr,formatter,args...);
      }
  #endif
    }
    template<const ConsoleColor color=NOPE,class... Args> inline void logln(const char *formatter,Args... args){
  #ifdef memset0
      if(~color){
        fprintf(stderr,"\033[%dm",30+color);
        fprintf(stderr,formatter,args...);
        fprintf(stderr,"\033[0m\n");
      }else{
        fprintf(stderr,formatter,args...);
        fprintf(stderr,"\n");
      }
  #endif
    }
    template<class T> inline void logs(const T &x){
  #ifdef memset0
      fprintf(stderr,container::to_string(x).c_str());
  #endif
    }
    template<class T,class... Args> inline void logs(const T &x,Args... args){
      logs(x),logs(args...);
    }
    template<class... Args> inline void logsln(Args... args){
      logs(args...);
  #ifdef memset0
      fprintf(stderr,"\n");
  #endif
    }
  }
  
  namespace fileio{
    inline void file_input(const char *dir){freopen(dir,"r",stdin);}
    inline void file_output(const char *dir){freopen(dir,"w",stdout);}
    inline void file_input(const std::string &dir){file_input(dir.c_str());}
    inline void file_output(const std::string &dir){file_output(dir.c_str());}
    inline void file_input(const container::string &dir){file_input(dir.c_str());}
    inline void file_output(const container::string &dir){file_output(dir.c_str());}

    template<class T> inline void file_io(const T name){
      using namespace container;
      file_input(name+".in"_s);
      file_output(name+".out"_s);
    }

    inline void fast_cpp_io(){
      std::ios::sync_with_stdio(0);
      std::cin.tie(0);
      std::cout.tie(0);
    }
  }

  #undef __integer_mapper
  #undef __float_mapper
  #undef __string_mapper
  #undef __string_join_mapper

  using namespace io;
  using namespace math;
  using namespace utils;
  using namespace modint;
  using namespace random;
  using namespace stdval;
  using namespace fileio;
  using namespace logger;
  using namespace container;
} // namespace mem

const int N=1<<19,mod=998244353;

namespace polynomial{
  namespace full{
    using u32=unsigned;
    using u64=unsigned long long;
    using z=mem::modint::Z<mod>;

    const u32 mod=::mod;
    z fac[N],ifac[N];
    
    inline z fpow(z a,int b){z s=1;for(;b;b>>=1,a=a*a)if(b&1)s=s*a;return s;}

    struct poly:mem::container::vector<z>{
      using mem::container::vector<z>::vector;
      inline void input(){
        for(int i=0;i<this->size();i++){
          mem::io::read(this->operator[](i).x);
        }
      }
      inline void output()const{
        for(int i=0;i<this->size();i++){
          mem::io::print(this->operator[](i).x);
          if(i+1!=this->size())mem::io::putc(' ');
        }
        mem::io::putc('\n');
      }
    };

    namespace SimpleNTT{
      u32 lim,shift,rev[N],w[N];
      u64 a[N];
      void dft_base_init(int N){
        for(int wn,len=1;len<N;len<<=1){
          wn=fpow(3,(mod-1)/(len<<1)).x,w[len]=1;
          for(int i=1;i<len;i++)w[i+len]=((u64)w[i+len-1]*wn)%mod;
        }
      }
      void dft_init(int len){
        lim=1,shift=0;
        while(lim<len)lim<<=1,++shift;
        for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(shift-1));
      }
      void dft(u32 *f){
        for(int i=0;i<lim;i++)a[rev[i]]=f[i];
        for(int len=1;len<lim;len<<=1){
          for(int i=0;i<lim;i+=(len<<1))
            for(int j=0;j<len;j++){
              u64 x=a[i+j],y=a[i+j+len]*w[j+len]%mod;
              a[i+j]=x+y,a[i+j+len]=x+mod-y;
            }
          if(len==131072)for(int i=0;i<lim;i++)a[i]%=mod;
        }
        for(int i=0;i<lim;i++)f[i]=(u32)(a[i]%mod);
      }
      void idft(u32 *f){
        dft(f);
        std::reverse(f+1,f+lim);
        u32 inv_lim=fpow((int)lim,mod-2).x;
        for(int i=0;i<lim;i++)f[i]=(u64)f[i]*inv_lim%mod;
      }
    }

    namespace FastNTT{ // source: skip2004, https://uoj.ac/submission/415571
      const u32 mod2=mod<<1;
      u32 lim,shift;
      struct multi_integer{
        u32 val,ival;
        inline multi_integer(){}
        inline explicit multi_integer(u32 v){val=v,ival=((u64)v<<32)/mod;}
        inline u32 operator*(u32 x)const{return val*x-u32((u64)x*ival>>32)*mod;}
      }wn[N|1],iwn[N|1];

      inline u32 get(u32 x){return ((u64)x<<32)/mod;}
      inline u32 norm1(u32 x){return x>=mod?x-mod:x;}
      inline u32 norm2(u32 x){return x>=mod2?x-mod2:x;}
      inline u32 pow(u32 a,u32 b,u32 ans=1){for(;b;b>>=1,a=(u64)a*a%mod)if(b&1)ans=(u64)ans*a%mod;return ans;}
      inline u32 multi(u32 w,u32 idx){return wn[idx]*w;}
      inline u32 div_lim(u32 x){return (x+(u64)(-x&lim-1)*mod)>>shift;}
      inline void fold(u32 *a){for(int i=0;i<lim;i++)if(a[i]>=mod)a[i]-=mod;}

      inline void dft_base_init(u32 len){
        u32 N=1; for(;N<len;)N<<=1;
        const u32 mid=N>>1,w=pow(3,mod/N),iw=pow((mod+1)/3,mod/N);
        wn[mid]=iwn[mid]=multi_integer(1);
        for(u32 i=1;i<mid;++i){
          wn[mid+i]=multi_integer((u64)wn[mid+i-1].val*w%mod);
          iwn[mid+i]=multi_integer((u64)iwn[mid+i-1].val*iw%mod);
        }
        for(u32 i=mid-1;(int)i>=0;--i)wn[i]=wn[i<<1],iwn[i]=iwn[i<<1];
      }
      inline void dft_init(u32 len){lim=1,shift=0;for(;lim<len;)lim<<=1,++shift;}

      inline void dft(u32 *a){
      #define trans(a,b,idx) { \
          const u32 A=norm2(a+b); \
          b=wn[idx]*(a+mod2-b),a=A; \
        }
      #define trans2(a,b) { \
          const u32 A=norm2(a+b); \
          b=norm2(a+mod2-b),a=A; \
        }
        if(lim==1)return;
        if(lim==2){trans(a[0],a[1],1);return fold(a);}
        if(lim==4){trans2(a[0],a[2])trans(a[1],a[3],3)trans(a[0],a[1],1)trans(a[2],a[3],1);return fold(a);}
        for(int mid=lim>>1;mid>2;mid>>=1)
          for(int j=0;j<lim;j+=mid+mid)
            for(int k=0;k<mid;k+=4){
              trans(a[j+k+0],a[mid+j+k+0],mid+k+0);
              trans(a[j+k+1],a[mid+j+k+1],mid+k+1);
              trans(a[j+k+2],a[mid+j+k+2],mid+k+2);
              trans(a[j+k+3],a[mid+j+k+3],mid+k+3);
            }
        for(int j=0;j<lim;j+=8){
          trans2(a[j+0],a[j+2])trans(a[j+1],a[j+3],3);
          trans2(a[j+4],a[j+6])trans(a[j+5],a[j+7],3);
        }
        for(int j=0;j<lim;j+=8){
          trans2(a[j+0],a[j+1])trans2(a[j+2],a[j+3]);
          trans2(a[j+4],a[j+5])trans2(a[j+6],a[j+7]);
        }
        for(int i=0;i<lim;i++)if(a[i]>=mod)a[i]-=mod;
        fold(a);
      #undef trans
      #undef trans2
      }

      inline void idft(u32 *a){
      #define trans(a,b,idx) { \
          u32 _a=a,_b=b,A=norm2(_a),B=iwn[idx]*_b; \
          a=A+B,b=A+mod2-B; \
        }
      #define trans2(a,b) { \
          const u32 A=norm2(a),B=norm2(b); \
          a=A+B,b=A+mod2-B; \
        }
        if(lim==1)return;
        if(lim==2){
          const u32 A=a[0],B=a[1];
          a[0]=div_lim(A+B),a[1]=div_lim(A+mod2-B);
          return fold(a);
        }
        if(lim==4){
          trans(a[0],a[1],1)trans(a[2],a[3],1)trans2(a[0],a[2])trans(a[1],a[3],3);
          a[0]=div_lim(a[0]),a[1]=div_lim(a[1]),a[2]=div_lim(a[2]),a[3]=div_lim(a[3]);
          return fold(a);
        }
        for(int j=0;j<lim;j+=8){
          trans2(a[j+0],a[j+1])trans2(a[j+2],a[j+3]);
          trans2(a[j+4],a[j+5])trans2(a[j+6],a[j+7]);
        }
        for(int j=0;j<lim;j+=8){
          trans2(a[j+0],a[j+2])trans(a[j+1],a[j+3],3);
          trans2(a[j+4],a[j+6])trans(a[j+5],a[j+7],3);
        }
        for(int mid=4;mid<lim;mid<<=1)
          for(int j=0;j<lim;j+=mid+mid)
            for(int k=0;k<mid;k+=4){
              trans(a[j+k+0],a[mid+j+k+0],mid+k+0);
              trans(a[j+k+1],a[mid+j+k+1],mid+k+1);
              trans(a[j+k+2],a[mid+j+k+2],mid+k+2);
              trans(a[j+k+3],a[mid+j+k+3],mid+k+3);
            }
        for(int i=0;i<lim;++i)a[i]=div_lim(a[i]);
        fold(a);
      #undef trans
      #undef trans2
      }
    }

    using namespace FastNTT;
    inline void dft(z *a){dft((u32*)a);}
    inline void idft(z *a){idft((u32*)a);}
    inline void dft(poly &a){a.resize(lim),dft((u32*)&a[0]);}
    inline void idft(poly &a){a.resize(lim),idft((u32*)&a[0]);}

    inline poly mul(poly a,poly b,int len=-1){
      if(!~len)len=(int)a.size()+(int)b.size()-1;
      dft_init((int)a.size()+(int)b.size()-1);
      dft(a),dft(b);
      for(int i=0;i<lim;i++)a[i]*=b[i];
      idft(a);
      return a.resize(len),a;
    }

    inline poly operator+(poly a,const poly &b){
      if(b.size()>a.size())a.resize(b.size());
      for(int i=0;i<b.size();i++)a[i]+=b[i];
      return a;
    }
    inline poly operator-(poly a,const poly &b){
      if(b.size()>a.size())a.resize(b.size());
      for(int i=0;i<b.size();i++)a[i]-=b[i];
      return a;
    }
    inline poly operator*(const poly &a,const poly &b){
      return mul(a,b,(int)a.size()+(int)b.size()-1);
    }

    struct PolynomialInit{PolynomialInit(){dft_base_init(N);}}_polynomial_initer;
  }
  using full::z;
  using full::poly;
  using full::dft_init;
  using full::dft;
  using full::idft;
  using full::mul;
}

using namespace mem;
using namespace polynomial;

int type,n;
z a[N],b[N],c[N],d[N],e[N],f[N],g[N];

void solve(int l,int r){
  if(l+1==r){
    if(l==1)g[l]=1;
//		for(int j=1;j<=l-1;j++)g[l]-=(j+1)*g[j]*g[l-j];
//		for(int j=2;j<=l-1;j++)g[l]-=j*g[j]*g[l-j+1];
    return;
  }
  int m=(l+r)>>1,n=(r-l)>>1;
  solve(l,m);
  using polynomial::full::lim;
  if(l==0){
    dft_init((n<<1)-1);
    for(int i=0;i<n;i++)b[i]=g[i]*i;
    memset(b+n,0,(lim-n)<<2),dft(b);
    for(int i=0;i<n;i++)c[i]=g[i];
    memset(c+n,0,(lim-n)<<2),dft(c);
    for(int i=0;i<lim;i++)a[i]=b[i]+c[i];
    for(int i=0;i<lim;i++)a[i]*=c[i],b[i]*=c[i];
    idft(a);
    idft(b);
    for(int i=0;i<n;i++)g[m+i]-=a[n+i];
    for(int i=0;i<n-1;i++)g[m+i]-=b[n+i+1];
  }else{
    dft_init(n*3);
    for(int i=0;i<n;i++)b[i]=g[i+l]*(i+l);
    memset(b+n,0,(lim-n)<<2),dft(b);
    for(int i=0;i<n;i++)c[i]=g[i+l];
    memset(c+n,0,(lim-n)<<2),dft(c);
    for(int i=0;i<lim;i++)a[i]=b[i]+c[i];
    for(int i=0;i<=(n<<1);i++)e[i]=g[i]*i;
    memset(e+(n<<1)+1,0,(lim-(n<<1)-1)<<2),dft(e);
    for(int i=0;i<=(n<<1);i++)f[i]=g[i];
    memset(f+(n<<1)+1,0,(lim-(n<<1)-1)<<2),dft(f);
    for(int i=0;i<lim;i++)d[i]=e[i]+f[i];
    for(int i=0;i<lim;i++)a[i]*=f[i],b[i]*=f[i];
    idft(a);
    idft(b);
    for(int i=0;i<lim;i++)d[i]*=c[i],e[i]*=c[i];
    idft(d);
    idft(e);
    for(int i=0;i<n;i++)g[m+i]-=a[n+i]+d[n+i];
    for(int i=0;i<n;i++)g[m+i]-=b[n+i+1]+e[n+i+1];
    if((n<<1)==l)g[(l<<1)-1]+=g[l]*g[l]*l;
  }
//	log("solve(%d,%d)=>%d\n",l,r,g[5].x);
  solve(m,r);
}

int main(){
#ifdef memset0
  freopen("1.in","r",stdin);
#endif
  read(type,n);
  int lim=1;
  while(lim<=n)lim<<=1;
  solve(0,lim);
//	for(int i=1;i<=n;i++)println(g[i]);
  for(int i=1;i<=n;i++)f[i]=(i&1?2:mod-2)-g[i];
  f[2]=2;
  for(int i=1;i<=n;i++)if(type||i==n)println(f[i]);
}