#ifndef INCLUDE_MODE
  #define INCLUDE_MODE
  // #define REACTIVE
  // #define USE_GETLINE
  /* #define SUBMIT_ONLY */
  #define DEBUG_OUTPUT
  #define SAMPLE_CHECK J
#endif
#ifdef INCLUDE_MAIN

VO Solve()
{
  CIN( int , N , M );
  RETURN( Answer( N )[( 1 << N ) - M] );
}
REPEAT_MAIN(1);

#else /* INCLUDE_MAIN */
#ifdef INCLUDE_SUB

/* COMPAREに使用。圧縮時は削除する。*/
using answer_type = vector<MP>;
answer_type Naive( int N , const bool& debug_output = true )
{
  answer_type a = {1,1};
  // f(n,m) = sum_{j=max((m>0?1:0),2^{n-1}-m)}^{min(m,2^{n-1})} binom(m,j)*binom(2^n-m,2^{n-1}-j)*f(n-1,j)*f(n-1,m-j)
  FOREQ( n , 1 , N ){
    vector<MP> na( ( 1 << n ) + 1 );
    FOREQ( m , 0 , 1 << n ){
      FOREQ( j , max( m > 0 ? 1 : 0 , m - ( 1 << ( n - 1 ) ) ) , min( m , 1 << ( n - 1 ) ) ){
        na[m] += MP::Combination( m , j ) * MP::Combination( ( 1 << n ) - m , ( 1 << ( n - 1 ) ) - j ) * a[j] * a[m - j];
      }
    }
    a = move( na );
  }
  return a;
}

answer_type Answer( int N , const bool& debug_output = true )
{
  // g(n,m) = sum_{j=(m>0?1:0)}^{min(m,2^{n-1})} g(n-1,j)*g(n-1,m-j)
  // g(n) = g(n-1)^2 - g(n-1,0)*g(n-1) + g(n-1,0)^2
  Polynomial<MP> g{{1,1}};
  FOREQ( n , 1 , N ){
    g = g * g - g * g[0] + g[0] * g[0];
  }
  answer_type a( ( 1 << N ) + 1 );
  FOREQ( d , 0 , 1 << N ){
    a[d] = g[d] * MP::Factorial( d ) * MP::Factorial( ( 1 << N ) - d );
  }
  return a;
}

/* 圧縮時は中身だけ削除する。*/
IN VO Experiment()
{
  // 1変数 ../Contest/Template/Experiment/OneVariable.txt
  // 2変数 ../Contest/Template/Experiment/TwoVariable.txt
  // 3変数 ../Contest/Template/Experiment/ThreeVariable.txt

  CEXPR( int , bound , 5 );
  int N_min = 1 , N_max = bound;
  vector<decldecay_t(Naive(0))> naive1( N_max - N_min + 1 );
  FOREQ( N , N_min , N_max ){
    naive1[N-N_min] = Naive( N , false );
    CERRNS( N , ": " , naive1[N-N_min] , "\n" );
  }
  CERRNS( "N∈[",N_min,"--",N_max,"]: " , naive1 , "\n" );
  // 2 1 2 24 6 8 12 24 40320 5040 4320 4320 5184 7200 11520 20160 40320 586493473 972509923 651771206 133783103 486850215 100007629 843587276 440000168 168590940 303263191 962977013 818010990 632502455 936481721 222947883 792368913 586493473 858512294 837902046 592305290 236922116 148798413 806727161 694870803 629973171 493848291 674027872 528188490 913781982 740541331 26795360 106109018 109924603 156266751 768549699 683431883 302994302 494405986 39240625 641919606 62290483 67585820 738215341 423288343 642880287 274799785 69397120 189350129 429256147 858512294
}

/* 圧縮時は中身だけ削除する。*/
IN VO SmallTest()
{
  // 数 ../Contest/Template/SmallTest/Number.txt
  // 配列 ../Contest/Template/SmallTest/Array.txt
  // 順列 ../Contest/Template/SmallTest/Permutation.txt
  // 文字列 ../Contest/Template/SmallTest/String.txt
  // グリッド ../Contest/Template/SmallTest/Grid.txt
  // グラフ ../Contest/Template/SmallTest/Graph.txt
  // 重み付きグラフ ../Contest/Template/SmallTest/WeightedGraph.txt
  // 区間クエリ ../Contest/Template/SmallTest/IntervalQuery.txt

  CEXPR( int , bound , 10 );
  int N_min = 1 , N_max = bound;
  FOREQ( N , N_min , N_max ){
    COMPARE( N );
    // // CHECK( N );
  }

  CERR( "全てのケースを確認しました。" );
}

/* 圧縮時は中身だけ削除する。*/
IN VO RandomTest( const int& test_case_num )
{
  // 数 ../Contest/Template/RandomTest/Number.txt
  // 配列 ../Contest/Template/RandomTest/Array.txt
  // 順列 ../Contest/Template/RandomTest/Permutation.txt
  // 文字列 ../Contest/Template/RandomTest/String.txt
  // グリッド ../Contest/Template/RandomTest/Grid.txt
  // グラフ ../Contest/Template/RandomTest/Graph.txt
  // 重み付きグラフ ../Contest/Template/RandomTest/WeightedGraph.txt
  // 区間クエリ ../Contest/Template/RandomTest/IntervalQuery.txt
  // 多種クエリ ../Contest/Template/RandomTest/MultiTypeQuery.txt
  REPEAT( test_case_num ){

  }
  CERR( "全てのケースを確認しました。" );
}

#define INCLUDE_MAIN
#include __FILE__
#else /* INCLUDE_SUB */
#ifdef INCLUDE_LIBRARY

/* VVV 常設でないライブラリは以下に挿入する。*/
// 常設ライブラリーのDynamicModsを消すか、DynamicModsの
// - CEXPR(uint,P,998244353);
// - US MP = DMOD;
// をコメントアウトする。
#ifdef DEBUG
  #include "c:/Users/user/Documents/Programming/Mathematics/Arithmetic/Mod/ConstexprModulo/Debug/a_Body.hpp"
#else
CEXPR(uint,P,998244353);
TE <uint M,TY INT> CE INT Residue(INT n)NE{RE MO(n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n < INT(M)?n:n %= M);}TE <TY INT> CE INT& ResidueP(INT& n)NE{CE CO uint trunc =(1 << 23)- 1;INT n_u = n >> 23;n &= trunc;INT n_uq =(n_u / 7)/ 17;n_u -= n_uq * 119;n += n_u << 23;RE n < n_uq?n += P - n_uq:n -= n_uq;}
TE <TY INT> IN INT ModularInverse(CO INT& base,ll c){AS(base > 0);ll a[2]={0,1 % base};INT b[2]={base,INT((c %= base)< 0?c += base:c)};WH(b[1]!= 0){CO INT q = b[0]/ b[1];(a[0]-= q * a[1]% base)< 0?a[0]+= base:a[0];b[0]-= q * b[1];swap(a[0],a[1]);swap(b[0],b[1]);}AS(b[0]== 1 &&(a[0]* c - 1)% base == 0);RE a[0];}
TE <uint M> CL Mod;TE <uint M>CL COantsForMod{PU:COantsForMod()= delete;ST CE CO uint g_memory_bound = 2e6;ST CE CO uint g_memory_le = M < g_memory_bound?M:g_memory_bound;ST CE uint g_M_minus = M - 1;ST CE int g_order = M - 1;ST CE int g_order_minus = g_order - 1;};
#define SFINAE_FOR_MOD enable_if_t<is_COructible_v<uint,decay_t<T>>>*
#define DC_OF_CM_FOR_MOD(OPR)CE bool OP OPR(CO Mod<M>& n)CO NE
#define DC_OF_AR_FOR_MOD(OPR,EX)CE Mod<M> OP OPR(Mod<M> n)CO EX;
#define DF_OF_CM_FOR_MOD(OPR)TE <uint M> CE bool Mod<M>::OP OPR(CO Mod<M>& n)CO NE{RE m_n OPR n.m_n;}
#define DF_OF_AR_FOR_MOD(OPR,EX,LEFT,OPR2)TE <uint M> CE Mod<M> Mod<M>::OP OPR(Mod<M> n)CO EX{RE MO(LEFT OPR2 ## = *TH);}TE <uint M,TY T,SFINAE_FOR_MOD = nullptr> CE Mod<M> OP OPR(T n0,CO Mod<M>& n1)EX{RE MO(Mod<M>(MO(n0))OPR ## = n1);}
TE <uint M>CL Mod{PU:uint m_n;CE Mod()NE;CE Mod(CO Mod<M>& n)NE;CE Mod(Mod<M>&& n)NE;TE <TY T,SFINAE_FOR_MOD = nullptr> CE Mod(T n)NE;CE Mod<M>& OP=(Mod<M> n)NE;CE Mod<M>& OP+=(CO Mod<M>& n)NE;CE Mod<M>& OP-=(CO Mod<M>& n)NE;CE Mod<M>& OP*=(CO Mod<M>& n)NE;IN Mod<M>& OP/=(Mod<M> n);CE Mod<M>& OP^=(ll EX);CE Mod<M>& OP<<=(ll n);CE Mod<M>& OP>>=(ll n);CE Mod<M>& OP++()NE;CE Mod<M> OP++(int)NE;CE Mod<M>& OP--()NE;CE Mod<M> OP--(int)NE;DC_OF_CM_FOR_MOD(==);DC_OF_CM_FOR_MOD(!=);DC_OF_CM_FOR_MOD(<);DC_OF_CM_FOR_MOD(<=);DC_OF_CM_FOR_MOD(>);DC_OF_CM_FOR_MOD(>=);DC_OF_AR_FOR_MOD(+,NE);DC_OF_AR_FOR_MOD(-,NE);DC_OF_AR_FOR_MOD(*,NE);DC_OF_AR_FOR_MOD(/,);CE Mod<M> OP^(ll EX)CO;CE Mod<M> OP<<(ll n)CO;CE Mod<M> OP>>(ll n)CO;CE Mod<M> OP-()CO NE;CE VO swap(Mod<M>& n)NE;CE CRUI RP()CO NE;ST CE Mod<M> DeRP(uint n)NE;ST IN CO Mod<M>& Factorial(CRL n);ST IN CO Mod<M>& FactorialInverse(CRL n);ST IN Mod<M> Combination(CRL n,CRL i);ST IN CO Mod<M>& zero()NE;ST IN CO Mod<M>& one()NE;ST CE uint GetModulo()NE;CE Mod<M>& SignInvert()NE;IN Mod<M>& Invert();CE Mod<M>& PPW(ll EX)NE;CE Mod<M>& NNPW(ll EX)NE;ST IN CO Mod<M>& Inverse(CRI n);ST IN CO Mod<M>& TwoPower(CRI n);ST IN CO Mod<M>& TwoPowerInverse(CRI n);US COants = COantsForMod<M>;};
US MP = Mod<P>;
TE <uint M> CE Mod<M>::Mod()NE:m_n(){}TE <uint M> CE Mod<M>::Mod(CO Mod<M>& n)NE:m_n(n.m_n){}TE <uint M> CE Mod<M>::Mod(Mod<M>&& n)NE:m_n(MO(n.m_n)){}TE <uint M> TE <TY T,SFINAE_FOR_MOD> CE Mod<M>::Mod(T n)NE:m_n(Residue<M>(MO(n))){}TE <uint M> CE Mod<M>& Mod<M>::OP=(Mod<M> n)NE{m_n = MO(n.m_n);RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::OP+=(CO Mod<M>& n)NE{(m_n += n.m_n)< M?m_n:m_n -= M;RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::OP-=(CO Mod<M>& n)NE{m_n < n.m_n?(m_n += M)-= n.m_n:m_n -= n.m_n;RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::OP*=(CO Mod<M>& n)NE{m_n = MO(ull(m_n)* n.m_n)% M;RE *TH;}TE <> CE MP& MP::OP*=(CO MP& n)NE{ull m_n_copy = m_n;m_n = MO((m_n_copy *= n.m_n)< P?m_n_copy:ResidueP(m_n_copy));RE *TH;}TE <uint M> IN Mod<M>& Mod<M>::OP/=(Mod<M> n){RE OP*=(n.Invert());}TE <uint M> CE Mod<M>& Mod<M>::PPW(ll EX)NE{Mod<M> pw{*TH};EX--;WH(EX != 0){(EX & 1)== 1?*TH *= pw:*TH;EX >>= 1;pw *= pw;}RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::NNPW(ll EX)NE{RE EX == 0?(m_n = 1,*TH):PPW(MO(EX));}TE <uint M> CE Mod<M>& Mod<M>::OP^=(ll EX){if(EX < 0){m_n = ModularInverse(M,MO(m_n));EX *= -1;}RE NNPW(MO(EX));}TE <uint M> CE Mod<M>& Mod<M>::OP<<=(ll n){RE *TH *=(n < 0 && -n < int(COants::g_memory_le))?TwoPowerInverse(- int(n)):(n >= 0 && n < int(COants::g_memory_le))?TwoPower(int(n)):Mod<M>(2)^= MO(n);}TE <uint M> CE Mod<M>& Mod<M>::OP>>=(ll n){RE *TH <<= MO(n *= -1);}TE <uint M> CE Mod<M>& Mod<M>::OP++()NE{m_n < COants::g_M_minus?++m_n:m_n = 0;RE *TH;}TE <uint M> CE Mod<M> Mod<M>::OP++(int)NE{Mod<M> n{*TH};OP++();RE n;}TE <uint M> CE Mod<M>& Mod<M>::OP--()NE{m_n == 0?m_n = COants::g_M_minus:--m_n;RE *TH;}TE <uint M> CE Mod<M> Mod<M>::OP--(int)NE{Mod<M> n{*TH};OP--();RE n;}DF_OF_CM_FOR_MOD(==);DF_OF_CM_FOR_MOD(!=);DF_OF_CM_FOR_MOD(>);DF_OF_CM_FOR_MOD(>=);DF_OF_CM_FOR_MOD(<);DF_OF_CM_FOR_MOD(<=);DF_OF_AR_FOR_MOD(+,NE,n,+);DF_OF_AR_FOR_MOD(-,NE,n.SignInvert(),+);DF_OF_AR_FOR_MOD(*,NE,n,*);DF_OF_AR_FOR_MOD(/,,n.Invert(),*);TE <uint M> CE Mod<M> Mod<M>::OP^(ll EX)CO{RE MO(Mod<M>(*TH)^= MO(EX));}TE <uint M> CE Mod<M> Mod<M>::OP<<(ll n)CO{RE MO(Mod<M>(*TH)<<= MO(n));}TE <uint M> CE Mod<M> Mod<M>::OP>>(ll n)CO{RE MO(Mod<M>(*TH)>>= MO(n));}TE <uint M> CE Mod<M> Mod<M>::OP-()CO NE{RE MO(Mod<M>(*TH).SignInvert());}TE <uint M> CE Mod<M>& Mod<M>::SignInvert()NE{m_n > 0?m_n = M - m_n:m_n;RE *TH;}TE <uint M> IN Mod<M>& Mod<M>::Invert(){m_n = m_n < COants::g_memory_le?Inverse(int(m_n)).m_n:ModularInverse(M,MO(m_n));RE *TH;}TE <uint M> CE VO Mod<M>::swap(Mod<M>& n)NE{std::swap(m_n,n.m_n);}TE <uint M> IN CO Mod<M>& Mod<M>::Inverse(CRI n){AS(0 < n && n < int(COants::g_memory_le));ST VE<Mod<M>> memory ={zero(),one()};ST int le_curr = 2;WH(le_curr <= n){memory.push_back(DeRP(M - memory[M % le_curr].m_n * ull(M / le_curr)% M));le_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::TwoPower(CRI n){AS(0 <= n && n < int(COants::g_memory_le));ST VE<Mod<M>> memory ={one()};ST int le_curr = 1;WH(le_curr <= n){memory.push_back(memory.back()+ memory.back());le_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::TwoPowerInverse(CRI n){AS(0 <= n && n < int(COants::g_memory_le));ST VE<Mod<M>> memory ={one()};ST int le_curr = 1;WH(le_curr <= n){auto& m = memory.back().m_n;memory.push_back(DeRP(((m & 1)== 0?m:m + M)>> 1));le_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::Factorial(CRL n){AS(n >= 0);if(ll(M)<= n){RE zero();}ST VE<Mod<M>> memory ={one(),one()};ST int le_curr = 2;WH(le_curr <= n){memory.push_back(memory[le_curr - 1]* le_curr);le_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::FactorialInverse(CRL n){AS(0 <= n && n < ll(M));ST VE<Mod<M>> memory ={one(),one()};ST int le_curr = 2;WH(le_curr <= n){memory.push_back(memory[le_curr - 1]* Inverse(le_curr));le_curr++;}RE memory[n];}TE <uint M> IN Mod<M> Mod<M>::Combination(CRL n,CRL i){RE 0 <= i && i <= n?Factorial(n)* FactorialInverse(i)* FactorialInverse(n - i):zero();}TE <uint M> CE CRUI Mod<M>::RP()CO NE{RE m_n;}TE <uint M> CE Mod<M> Mod<M>::DeRP(uint n)NE{Mod<M> n_copy{};n_copy.m_n = MO(n);RE n_copy;}TE <uint M> IN CO Mod<M>& Mod<M>::zero()NE{ST CE CO Mod<M> z{};RE z;}TE <uint M> IN CO Mod<M>& Mod<M>::one()NE{ST CE CO Mod<M> o{1};RE o;}TE <uint M> CE uint Mod<M>::GetModulo()NE{RE M;}TE <uint M> IN Mod<M> Inverse(CO Mod<M>& n){RE MO(Mod<M>(n).Invert());}TE <uint M> CE Mod<M> Power(Mod<M> n,ll EX){RE MO(n ^= MO(EX));}TE <uint M> CE VO swap(Mod<M>& n0,Mod<M>& n1)NE{n0.swap(n1);}TE <uint M> IN string to_string(CO Mod<M>& n)NE{RE to_string(n.RP())+ " + " + to_string(M)+ "Z";}TE <uint M,CL Traits> IN IS& OP>>(IS& is,Mod<M>& n){ll m;is >> m;n = m;RE is;}TE <uint M,CL Traits> IN OS& OP<<(OS& os,CO Mod<M>& n){RE os << n.RP();}

#ifndef DF_OF_HASH_FOR_MOD
#define DF_OF_HASH_FOR_MOD(MOD)IN size_t hash<MOD>::OP()(CO MOD& n)CO{ST CO hash<decldecay_t(n.RP())> h;RE h(n.RP());}
#endif
TE <uint M> DC_OF_HASH(Mod<M>);TE <uint M> DF_OF_HASH_FOR_MOD(Mod<M>);
#endif

#define PO Polynomial
#define FPS FormalPowerSeries
#ifdef DEBUG
  #include "c:/Users/user/Documents/Programming/Mathematics/Polynomial/FPS/a_Body.hpp"
#else
// 先にConstexprModuloを貼る。
ST_AS( is_same_v<MP,Mod<P>> );
TE <TY INT> CE INT Log(INT N){INT AN = 0,pw = 1;WH(N > pw){pw <<= 1;AN++;}RE AN;}

TE <TY T,int EX_lim>CL Power3Power_CE{PU:T m_val[EX_lim];CE Power3Power_CE(CO T& t);CE CO T& OP[](CRI i)CO;CE CO T(&Get()CO)[EX_lim];};
TE <TY T,int EX_lim> CE Power3Power_CE<T,EX_lim>::Power3Power_CE(CO T& t):m_val(){T pw{t};for(uint EX = EX_lim - 1;EX + 1 > 0;EX--){m_val[EX]= -pw;m_val[EX]*= pw *= pw;}}TE <TY T,int EX_lim> CE CO T& Power3Power_CE<T,EX_lim>::OP[](CRI i)CO{AS(i < EX_lim);RE m_val[i];}TE <TY T,int EX_lim> CE CO T(&Power3Power_CE<T,EX_lim>::Get()CO)[EX_lim]{RE m_val;}

// PO
#define DC_OF_AR_FOR_PO(FUNC)IN PO<T> OP FUNC(PO<T> f)CO;IN PO<T> OP FUNC(T t)CO
#define DF_OF_AR_FOR_PO(FUNC,DEF)TE <TY T> IN PO<T> PO<T>::OP FUNC(PO<T> f)CO{RE MO(DEF);};TE <TY T> IN PO<T> PO<T>::OP FUNC(T t)CO{RE *TH FUNC PO<T>(MO(t));}
TE <TY T>CL PO{PU:VE<T> m_f;int m_SZ;IN PO();IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(VE<T> f);IN PO(T t);IN PO(CRI i,T t);IN PO<T>& OP=(T n);IN PO<T>& OP=(PO<T> f);IN PO<T>& OP=(VE<T> f);IN CO T& OP[](CRI i)CO;IN T& OP[](CRI i);T OP()(CO T& t)CO;PO<T>& OP+=(CO PO<T>& f);PO<T>& OP-=(CO PO<T>& f);PO<T>& OP*=(PO<T> f);IN PO<T>& OP/=(CO PO<T>& f);PO<T>& OP/=(CO T& t);PO<T>& OP%=(CO PO<T>& f);PO<T>& OP%=(CO T& t);bool OP==(CO PO<T>& f)CO;bool OP==(CO T& t)CO;TE <TY P> IN bool OP!=(CO P& f)CO;DC_OF_AR_FOR_PO(+);IN PO<T> OP-()CO;DC_OF_AR_FOR_PO(-);DC_OF_AR_FOR_PO(*);IN PO<T> OP/(CO PO<T>& f)CO;IN PO<T> OP/(CO T& t)CO;IN PO<T> OP%(CO PO<T>& f)CO;IN PO<T> OP%(CO T& t)CO;IN CO VE<T>& GetCoefficient()CO NE;IN CRI SZ()CO NE;IN VO resize(CRI deg_plus)NE;int Valuation()CO NE;IN VO swap(PO<T>& f);IN VO swap(VE<T>& f);VO Reduce();VO TP(CRI N_trunc);ST PO<T> NaiveCN(PO<T> f0,CRI valuation0,CO PO<T>& f1,CRI valuation1,CRI N_trunc);ST PO<T> NaiveQuotient(PO<T> f0,CO PO<T>& f1);ST PO<T> NaiveResidue(PO<T> f0,CO PO<T>& f1);ST IN CO PO<T>& zero();ST IN CO PO<T>& one();ST IN CO PO<T>& x();ST IN CO T& c_zero();ST IN CO T& c_one();ST IN CO T& c_minus_one();IN PO<T>& SignInvert();};

// FPS
TE <TY T>CL FPS:PU PO<T>{PU:int m_N;IN FPS(CRI N = 0);IN FPS(CO FPS<T>& f);IN FPS(FPS<T>&& f);IN FPS(CRI N,T t);IN FPS(CRI N,CO PO<T>& f);IN FPS(CRI N,PO<T>&& f);IN FPS(CRI N,VE<T>&& f);IN FPS(CRI N,CRI i,T t);IN FPS<T>& OP=(FPS<T> f);IN FPS<T>& OP=(T n);IN FPS<T>& OP=(PO<T> f);IN FPS<T>& OP+=(CO T& t);FPS<T>& OP+=(CO PO<T>& f);IN FPS<T>& OP+=(CO FPS<T>& f);IN FPS<T>& OP-=(CO T& t);FPS<T>& OP-=(CO PO<T>& f);IN FPS<T>& OP-=(CO FPS<T>& f);IN FPS<T>& OP*=(CO T& t);FPS<T>& OP*=(PO<T> f);IN FPS<T>& OP*=(FPS<T> f);IN FPS<T>& OP/=(CO T& t);IN FPS<T>& OP/=(CO FPS<T>& t);TE <TY P> IN FPS<T> OP+(CO P& f)CO;IN FPS<T> OP-()CO;TE <TY P> IN FPS<T> OP-(CO P& f)CO;TE <TY P> IN FPS<T> OP*(CO P& f)CO;TE <TY P> IN FPS<T> OP/(CO P& f)CO;FPS<T> Inverse()CO;IN VO SetTruncation(CRI N)NE;IN CRI GetTruncation()CO NE;IN FPS<T>& TruncateInitial(CRI N)NE;IN FPS<T>& TruncateFinal(CRI N)NE;};
TE <TY T>US FPS = FPS<T>;

// FFT
#define PS_FOR_FFT_BODY(MOD,LE,PR,IPR,TYPE)ST_AS((TYPE::DeRP(PR)*= TYPE::DeRP(IPR))== TYPE::DeRP(1));TE <> CE CO uint LimitOfPowerForFFT<TYPE> = LE - 1;TE <> IN CO TYPE(&PrimitiveRootOfTwoForFFT()NE)[LimitOfPowerForFFT<TYPE>]{ST CE Power3Power_CE<TYPE,LimitOfPowerForFFT<TYPE>> PRT{PR};ST_AS(PRT.m_val[0]== TYPE::DeRP(1));RE PRT.Get();}TE <> IN CO TYPE(&InversePrimitiveRootOfTwoForFFT()NE)[LimitOfPowerForFFT<TYPE>]{ST CE Power3Power_CE<TYPE,LimitOfPowerForFFT<TYPE>> IPRT{IPR};ST_AS(IPRT.m_val[0]== TYPE::DeRP(1)&&(TYPE::DeRP(PR)*= TYPE::DeRP(IPR))== TYPE::DeRP(1));RE IPRT.Get();}TE <> IN PO<TYPE>& PO<TYPE>::OP*=(PO<TYPE> f){CO int SZ = m_SZ + f.m_SZ - 1;RE *TH = FFTCN(MO(*TH),MO(f),SZ);}TE <> IN PO<TYPE>& PO<TYPE>::OP/=(CO PO<TYPE>& f){AS(f.m_SZ > 0 && f[f.m_SZ-1]!= c_zero());Reduce();if(m_SZ < f.m_SZ){RE *TH = zero();}RE *TH = FFTQuotient(MO(*TH),f);}TE <> IN PO<TYPE>& PO<TYPE>::OP%=(CO PO<TYPE>& f){AS(f.m_SZ > 0 && f[f.m_SZ-1]!= c_zero());Reduce();RE *TH = FFTResidue(MO(*TH),f);}
#define PS_FOR_FFT(MOD,LE,PR,IPR,MINT)PS_FOR_FFT_BODY(MOD,LE,PR,IPR,MINT<MOD>)
TE <TY T> CE CO int LimitOfPowerForFFT;TE <TY T> IN CO T(&PrimitiveRootOfTwoForFFT()NE)[LimitOfPowerForFFT<T>];TE <TY T> IN CO T(&InversePrimitiveRootOfTwoForFFT()NE)[LimitOfPowerForFFT<T>];
TE <TY T>VO CooleyTukey(VE<T>& f,CRI N_shift,CRI N_input_start,CRI N_input_lim,CRI N_trunc,CRI two_pw,CRI EX,CO T(&PRT)[LimitOfPowerForFFT<T>]){AS(N_input_lim - N_input_start <= two_pw);CO int N_zero = N_shift + N_input_start,le = N_zero + two_pw;AS(N_zero <= N_trunc);CO int N_input_final = min(N_input_start + two_pw,int(f.SZ()));for(int i = N_input_lim;i < N_input_final;i++){f[i]= T{};}WH(int(f.SZ())< le){f.push_back(T{});}ST VE<int> bit_reverse[32]={VE<int>(1)};ST int e_next = 1;ST int two_pw_next = 1;ST int two_pw_next2 = 2;ST VE<int>* p_bit_reverse_prev = bit_reverse;ST VE<int>* p_bit_reverse_curr = p_bit_reverse_prev + 1;WH(e_next <= EX){*p_bit_reverse_curr = VE<int>(two_pw_next2);int* p_bit_reverse_curr_i = &((*p_bit_reverse_curr)[0]);int* p_bit_reverse_curr_i_plus = p_bit_reverse_curr_i + two_pw_next;int* p_bit_reverse_prev_i = &((*p_bit_reverse_prev)[0]);for(int i = 0;i < two_pw_next;i++){(*(p_bit_reverse_curr_i_plus++)= *(p_bit_reverse_curr_i++)= *(p_bit_reverse_prev_i++)* 2)+= 1;}e_next++;swap(two_pw_next,two_pw_next2);two_pw_next2 *= 4;p_bit_reverse_prev++;p_bit_reverse_curr++;}CO VE<int>& bit_reverse_EX = bit_reverse[EX];int bit_num = 0;CO int* p_bit_num_reverse = &(bit_reverse_EX[bit_num]);WH(bit_num < two_pw){if(*p_bit_num_reverse < bit_num){swap(f[*p_bit_num_reverse + N_input_start],f[bit_num + N_input_start]);}bit_num++;p_bit_num_reverse++;}CO T& one = PRT[0];T zeta,diff;int i,j,j_lim,two_pw_curr = 1,two_pw_curr_2 = 2;WH(two_pw_curr < two_pw){CO int N_input_final_curr = N_input_start + two_pw_curr;bit_num = 0;i = 0;zeta = one;WH(i < two_pw){j = i;j_lim = i + two_pw_curr;WH(j < j_lim){diff = f[j + N_input_start]- f[j + N_input_final_curr];f[j + N_input_start]+= f[j + N_input_final_curr];f[j + N_input_final_curr]= zeta * diff;j++;}bit_num++;i += two_pw_curr_2;j = 0;WH(true){if(((bit_num >> j)& 1)== 1){zeta *= PRT[j+1];break;}j++;}}two_pw_curr <<= 1;two_pw_curr_2 <<= 1;}if(N_trunc < le){f.resize(N_trunc);}if(N_shift > 0){for(int i = N_trunc - 1;i >= N_zero;i--){f[i]= MO(f[i - N_shift]);}for(int i = N_zero - 1;i >= N_input_start;i--){f[i]= T{};}}RE;}TE <TY T> IN VO FFT(VE<T>& f,CRI N_input_start,CRI N_input_lim,CRI two_pw,CRI EX){CooleyTukey<T>(f,0,N_input_start,N_input_lim,N_input_start + two_pw,two_pw,EX,PrimitiveRootOfTwoForFFT<T>());}TE <TY T> IN VO IFFT(VE<T>& f,CRI N_shift,CRI N_input_start,CRI N_input_lim,CRI N_trunc,CRI two_pw,CO T& two_pw_inv,CRI EX){CooleyTukey<T>(f,N_shift,N_input_start,N_input_lim,N_trunc,two_pw,EX,InversePrimitiveRootOfTwoForFFT<T>());CO int SZ = f.SZ();for(int i = N_shift + N_input_start;i < SZ;i++){f[i]*= two_pw_inv;}}TE <TY T>PO<T> FFTCN(PO<T> f0,PO<T> f1,CRI N_trunc){f0.Reduce();if(f0.m_SZ == 0){RE MO(f0);}f1.Reduce();if(f1.m_SZ == 0){RE MO(f1);}AS(f0.m_SZ <= N_trunc);CO int valuation0 = f0.Valuation();CO int valuation1 = f1.Valuation();if(N_trunc <= valuation0 + valuation1){RE f0.zero();}CO int le0 = f0.m_SZ - valuation0;CO int le1 = min(f1.m_SZ,N_trunc)- valuation1;CO int le = le0 + le1 - 1;CO int EX = Log(le);if(min(le0,le1)<= EX){RE f0.NaiveCN(MO(f0),valuation0,MO(f1),valuation1,min(f0.m_SZ + f1.m_SZ - 1,N_trunc));}CO int two_pw = 1 << EX;FFT(f0.m_f,valuation0,f0.m_SZ,two_pw,EX);FFT(f1.m_f,valuation1,valuation1 + le1,two_pw,EX);for(int i = 0;i < two_pw;i++){f0.m_f[i + valuation0]*= f1.m_f[i + valuation1];}IFFT(f0.m_f,valuation1,valuation0,valuation0 + two_pw,N_trunc,two_pw,f0.c_one()/ two_pw,EX);f0.m_SZ = f0.m_f.SZ();RE MO(f0);}TE <TY T>PO<T> FFTQuotient(PO<T> f0,PO<T> f1){AS(f1.m_SZ > 0 && f1[f1.m_SZ-1]!= f0.c_zero());if(f0.m_SZ < f1.m_SZ){RE PO<T>::zero();}CO int f0_TP_SZ = f0.m_SZ - f1.m_SZ + 1;CO int f1_TP_SZ = min(f0_TP_SZ,f1.m_SZ);f1.TP(f1_TP_SZ);CO FPS<T> f1_TP_inverse = FPS<T>(f0_TP_SZ,MO(f1)).Inverse();f0.TP(f0_TP_SZ);FPS<T> f0_TP{f0_TP_SZ,MO(f0)};f0_TP *= f1_TP_inverse;f0_TP.TP(f0_TP_SZ);RE f0_TP;}TE <TY T>PO<T> FFTResidue(PO<T> f0,CO PO<T>& f1){if(f0.m_SZ >= f1.m_SZ){f0 -=(f0 / f1)* f1;f0.Reduce();}RE MO(f0);}
PS_FOR_FFT(P,24,31,128805723,Mod);
PS_FOR_FFT(167772161,26,17,29606852,Mod);
PS_FOR_FFT(469762049,27,30,15658735,Mod);
PS_FOR_FFT(754974721,25,362,415027540,Mod);

// FPS
TE <TY T> IN FPS<T>::FPS(CRI N):PO<T>(),m_N(N){AS(m_N > 0);}TE <TY T> IN FPS<T>::FPS(CO FPS<T>& f):PO<T>(f),m_N(f.m_N){}TE <TY T> IN FPS<T>::FPS(FPS<T>&& f):PO<T>(MO(f.m_f)),m_N(f.m_N){}TE <TY T> IN FPS<T>::FPS(CRI N,T t):PO<T>(MO(t)),m_N(N){AS(m_N > 0);}TE <TY T> IN FPS<T>::FPS(CRI N,CO PO<T>& f):PO<T>(),m_N(N){AS(m_N > 0);TH->m_SZ = f.m_SZ < m_N?f.m_SZ:m_N;TH->m_f = VE<T>(TH->m_SZ);for(int i = 0;i < TH->m_SZ;i++){TH->m_f[i]= f.m_f[i];}}TE <TY T> IN FPS<T>::FPS(CRI N,PO<T>&& f):PO<T>(),m_N(N){if(f.m_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f.m_SZ > m_N){TruncateFinal(m_N);}}else{TH->m_f = VE<T>(m_N);for(int i = 0;i < m_N;i++){TH->m_f[i]= MO(f.m_f[i]);}TH->m_SZ = m_N;}}TE <TY T> IN FPS<T>::FPS(CRI N,VE<T>&& f):PO<T>(),m_N(N){AS(m_N > 0);CO int f_SZ = f.SZ();if(f_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f_SZ > m_N){TruncateFinal(m_N);}}else{TH->m_f = VE<T>(m_N);for(int i = 0;i < m_N;i++){TH->m_f[i]= MO(f[i]);}}}TE <TY T> IN FPS<T>::FPS(CRI N,CRI i,T t):PO<T>(),m_N(N){AS(m_N > 0);if(i < m_N?t != TH->c_zero():false){(*TH)[i]= MO(t);}}TE <TY T> IN FPS<T>& FPS<T>::OP=(FPS<T> f){PO<T>::OP=(MO(f.m_f));m_N = f.m_N;RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP=(T n){PO<T>::OP=(MO(n));RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP=(PO<T> f){RE OP=(FPS<T>(m_N,MO(f)));}TE <TY T> IN FPS<T>& FPS<T>::OP+=(CO T& t){PO<T>::OP+=(t);RE *TH;}TE <TY T>FPS<T>& FPS<T>::OP+=(CO PO<T>& f){CRI SZ_f = m_N < f.m_SZ?m_N:f.m_SZ;CRI SZ = TH->m_SZ < SZ_f?TH->m_SZ:SZ_f;for(int i = 0;i < SZ;i++){TH->m_f[i]+= f.m_f[i];}for(int i = SZ;i < SZ_f;i++){TH->m_f.push_back(f.m_f[i]);}TH->m_SZ = TH->m_f.SZ();RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP+=(CO FPS<T>& f){AS(m_N <= f.m_N);CO PO<T>& f_ref = f;RE OP+=(f_ref);}TE <TY T> IN FPS<T>& FPS<T>::OP-=(CO T& t){PO<T>::OP-=(t);RE *TH;}TE <TY T>FPS<T>& FPS<T>::OP-=(CO PO<T>& f){CRI SZ_f = m_N < f.m_SZ?m_N:f.m_SZ;CRI SZ = TH->m_SZ < SZ_f?TH->m_SZ:SZ_f;for(int i = 0;i < SZ;i++){TH->m_f[i]-= f.m_f[i];}for(int i = SZ;i < SZ_f;i++){TH->m_f.push_back(-f.m_f[i]);}TH->m_SZ = TH->m_f.SZ();RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP-=(CO FPS<T>& f){AS(m_N <= f.m_N);CO PO<T>& f_ref = f;RE OP-=(f_ref);}TE <TY T> IN FPS<T>& FPS<T>::OP*=(CO T& t){PO<T>::OP*=(t);RE *TH;}TE <TY T>FPS<T>& FPS<T>::OP*=(PO<T> f){*TH = FFTCN(forward<PO<T>>(*TH),MO(f),m_N);RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP*=(FPS<T> f){AS(m_N <= f.m_N);RE OP*=(forward<PO<T>>(f));}TE <TY T> IN FPS<T>& FPS<T>::OP/=(CO T& t){PO<T>::OP/=(t);RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::OP/=(CO FPS<T>& f){AS(m_N <= f.m_N);RE OP*=(m_N == f.m_N?f.Inverse():FPS<T>(m_N,f).Inverse());}TE <TY T> TE <TY P> IN FPS<T> FPS<T>::OP+(CO P& f)CO{RE MO(FPS<T>(*TH)+= f);}TE <TY T> IN FPS<T> FPS<T>::OP-()CO{RE MO(FPS<T>(m_N)-= *TH);}TE <TY T> TE <TY P> IN FPS<T> FPS<T>::OP-(CO P& f)CO{RE MO(FPS<T>(*TH)-= f);}TE <TY T> TE <TY P> IN FPS<T> FPS<T>::OP*(CO P& f)CO{RE MO(FPS<T>(*TH)*= f);}TE <TY T> TE <TY P> IN FPS<T> FPS<T>::OP/(CO P& f)CO{RE MO(FPS<T>(*TH)/= f);}TE <TY T>FPS<T> FPS<T>::Inverse()CO{AS(TH->m_SZ > 0 && TH->m_f[0]!= TH->c_zero());CO PO<T>& TH_ref = *TH;int pw;int pw_2 = 1;FPS<T> f_inv{pw_2,TH->c_one()/ TH->m_f[0]};WH(pw_2 < m_N){pw = pw_2;pw_2 <<= 1;f_inv.SetTruncation(pw_2);auto temp = f_inv * TH_ref;temp[0]--;temp *= f_inv;for(int i = pw;i < pw_2;i++){f_inv[i]-= temp[i];}}f_inv.SetTruncation(m_N);RE f_inv;}TE <TY T> IN VO FPS<T>::SetTruncation(CRI N)NE{if(N < m_N){TruncateFinal(N);}m_N = N;}TE <TY T> IN CRI FPS<T>::GetTruncation()CO NE{RE m_N;}TE <TY T> IN FPS<T>& FPS<T>::TruncateInitial(CRI N)NE{CRI SZ = N < TH->m_SZ?N:TH->m_SZ;for(int i = 0;i < SZ;i++){TH->m_f[i]= 0;}RE *TH;}TE <TY T> IN FPS<T>& FPS<T>::TruncateFinal(CRI N)NE{WH(TH->m_SZ > N){TH->m_f.pop_back();TH->m_SZ--;}RE *TH;}TE <TY T>FPS<T> Differential(CO FPS<T>& f){auto& SZ = f.SZ();auto& N = f.GetTruncation();if(SZ < 1){RE FPS<T>(1 < N?N - 1:1);}VE<T> df(SZ - 1);for(int i = 1;i < SZ;i++){df[i - 1]= f[i]* i;}RE FPS<T>(1 < N?N - 1:1,MO(df));}TE <TY T>FPS<T> Differential(CRI n,CO FPS<T>& f){if(n == 0){RE f;}if(n == 1){RE Differential<T>(f);}auto& SZ = f.SZ();auto& N = f.GetTruncation();if(SZ < n){RE FPS<T>(n < N?N - n:1);}VE<T> df(SZ - n);T coef = T::Factorial(n),numer = n,denom = 0;for(int i = n;i < SZ;i++){df[i - n]= f[i]* coef;(coef *= ++numer)/= ++denom;}RE FPS<T>(n < N?N - n:1,MO(df));}TE <TY T>FPS<T> ShiftedIntegral(CRI n,CO FPS<T>& f,CRI shift){auto& SZ = f.SZ();auto& N = f.GetTruncation();if(SZ + n < shift){RE FPS<T>{N + n > shift?N + n - shift:1};}VE<T> F(SZ + n - shift);if(n == 0){for(int i = shift;i < SZ;i++){F[i - shift]= f[i];}}else if(n == 1){CO int i_min = max(shift - 1,0);T denom = i_min;for(int i = i_min;i < SZ;i++){F[i + 1 - shift]= f[i]/ ++denom;}}else{CO int i_min = max(shift - n,0);for(int i = i_min;i < SZ;i++){F[i + n - shift]= f[i]* T::Factorial(i)* T::FactorialInverse(n + i);}}RE FPS<T>(N + n - shift,MO(F));}TE <TY T> IN FPS<T> Integral(CO FPS<T>& f){RE ShiftedIntegral<T>(1,f,0);}TE <TY T> IN FPS<T> Integral(CRI n,CO FPS<T>& f){RE ShiftedIntegral<T>(n,f,0);}TE <TY T>FPS<T> Exp(CO FPS<T>& f){AS(f[0]== f.c_zero());CRI N = f.GetTruncation();int pw;int pw_2 = 1;FPS<T> f_exp{pw_2,f.c_one()};WH(pw_2 < N){pw = pw_2;pw_2 *= 2;f_exp.SetTruncation(pw_2);auto temp = Differential<T>(f_exp);temp /= f_exp;temp = ShiftedIntegral(1,temp,pw);for(int i = 0;i < pw;i++){temp[i]-= f[i | pw];}temp *= f_exp;for(int i = 0;i < pw;i++){f_exp[i|pw]-= temp[i];}}f_exp.SetTruncation(N);RE f_exp;}TE <TY T> IN FPS<T> Log(CO FPS<T>& f){AS(f[0]== f.c_one());RE Integral<T>(Differential<T>(f)/= f);}TE <TY T,CL Traits> IN OS& OP<<(OS& os,CO FPS<T>& f){CO int N = f.GetTruncation();for(int i = 0;i < N;i++){(i > 0?os << " ":os)<< f[i];}RE os;}

// PO
TE <TY T> IN PO<T>::PO():m_f(),m_SZ(0){}TE <TY T> IN PO<T>::PO(CO PO<T>& f):m_f(f.m_f),m_SZ(f.m_SZ){}TE <TY T> IN PO<T>::PO(PO<T>&& f):m_f(MO(f.m_f)),m_SZ(f.m_SZ){}TE <TY T> IN PO<T>::PO(VE<T> f):m_f(MO(f)),m_SZ(m_f.SZ()){}TE <TY T> IN PO<T>::PO(T t):PO(){if(t != c_zero()){OP[](0)= MO(t);}}TE <TY T> IN PO<T>::PO(CRI i,T t):PO(){if(t != c_zero()){OP[](i)= MO(t);}}TE <TY T> IN PO<T>& PO<T>::OP=(T n){m_f.clear();m_SZ = 0;OP[](0)= MO(n);RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(PO<T> f){m_f = MO(f.m_f);m_SZ = f.m_SZ;RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(VE<T> f){m_f = MO(f);m_SZ = m_f.SZ();RE *TH;}TE <TY T> IN CO T& PO<T>::OP[](CRI i)CO{RE m_SZ <= i?c_zero():m_f[i];}TE <TY T> IN T& PO<T>::OP[](CRI i){if(m_SZ <= i){CO T& z = c_zero();WH(m_SZ <= i){m_f.push_back(z);m_SZ++;}}RE m_f[i];}TE <TY T> T PO<T>::OP()(CO T& t)CO{T AN =(*TH)[0];T t_pw = c_one();for(int d = 1;d < m_SZ;d++){AN += m_f[d]*(t_pw *= t);}RE AN;}TE <TY T>PO<T>& PO<T>::OP+=(CO PO<T>& f){if(m_SZ < f.m_SZ){for(int i = 0;i < m_SZ;i++){m_f[i]+= f.m_f[i];}for(int i = m_SZ;i < f.m_SZ;i++){m_f.push_back(f.m_f[i]);}m_SZ = f.m_SZ;}else{for(int i = 0;i < f.m_SZ;i++){m_f[i]+= f.m_f[i];}}RE *TH;}TE <TY T>PO<T>& PO<T>::OP-=(CO PO<T>& f){if(m_SZ < f.m_SZ){for(int i = 0;i < m_SZ;i++){m_f[i]-= f.m_f[i];}for(int i = m_SZ;i < f.m_SZ;i++){m_f.push_back(- f.m_f[i]);}m_SZ = f.m_SZ;}else{for(int i = 0;i < f.m_SZ;i++){m_f[i]-= f.m_f[i];}}RE *TH;}TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == c_one()){RE *TH;}CO T t_inv{c_one()/ t};for(int i = 0;i < m_SZ;i++){OP[](i)*= t_inv;}RE *TH;}TE <TY T>PO<T>& PO<T>::OP%=(CO T& t){if(t == c_one()){RE *TH = zero();}for(int i = 0;i < m_SZ;i++){m_f[i]%= t;}RE *TH;}TE <TY T>bool PO<T>::OP==(CO PO<T>& f)CO{CRI SZ0 = SZ();CRI SZ1 = f.SZ();CRI SZ_max = SZ0 < SZ1?SZ1:SZ0;for(int i = 0;i < SZ_max;i++){if(OP[](i)!= f[i]){RE false;}}RE true;}TE <TY T>bool PO<T>::OP==(CO T& t)CO{CRI SZ_max = SZ();CO T& zero = PO<T>::c_zero();for(int i = 1;i < SZ_max;i++){if(m_f[i]!= zero){RE false;}}RE OP[](0)== t;}TE <TY T> TE<TY P> IN bool PO<T>::OP!=(CO P& f)CO{RE !(*TH == f);}DF_OF_AR_FOR_PO(+,f += *TH);TE <TY T> IN PO<T>& PO<T>::SignInvert(){Reduce();for(auto& fi:m_f){fi = -fi;}RE *TH;}TE <TY T> IN PO<T> PO<T>::OP-()CO{RE MO(PO<T>(*TH).SignInvert());}DF_OF_AR_FOR_PO(-,f.SignInvert()+= *TH);DF_OF_AR_FOR_PO(*,f *= *TH);TE <TY T> IN PO<T> PO<T>::OP/(CO T& t)CO{RE MO(PO<T>(*TH)/= t);}TE <TY T> IN PO<T> PO<T>::OP/(CO PO<T>& f)CO{RE MO(PO<T>(*TH)/= f);}TE <TY T> IN PO<T> PO<T>::OP%(CO T& t)CO{RE MO(PO<T>(*TH)%= t);}TE <TY T> IN PO<T> PO<T>::OP%(CO PO<T>& f)CO{RE MO(PO<T>(*TH)%= f);}TE <TY T> IN CO VE<T>& PO<T>::GetCoefficient()CO NE{RE m_f;}TE <TY T> IN CRI PO<T>::SZ()CO NE{RE m_SZ;}TE <TY T> IN VO PO<T>::resize(CRI deg_plus)NE{m_f.resize(m_SZ = deg_plus);}TE <TY T>int PO<T>::Valuation()CO NE{for(int i = 0;i < m_SZ;i++){if(m_f[i]!= c_zero()){RE i;}}RE -1;}TE <TY T> IN VO PO<T>::swap(PO<T>& f){m_f.swap(f.m_f);swap(m_SZ,f.m_SZ);}TE <TY T> IN VO PO<T>::swap(VE<T>& f){m_f.swap(f);m_SZ = m_f.SZ();}TE <TY T>VO PO<T>::Reduce(){CO T& z = c_zero();WH(m_SZ > 0 && m_f[m_SZ - 1]== z){m_f.pop_back();m_SZ--;}RE;}TE <TY T>VO PO<T>::TP(CRI N_trunc){WH(N_trunc > m_SZ){m_f.push_back(c_zero());m_SZ++;}CO int N_half = min(N_trunc,(m_SZ + 1)/ 2);for(int d = 0;d < N_half;d++){::swap(m_f[d],m_f[m_SZ - 1 - d]);}m_f.resize(N_trunc);m_SZ = N_trunc;RE;}TE <TY T> IN CO PO<T>& PO<T>::zero(){ST CO PO<T> z{};RE z;}TE <TY T> IN CO PO<T>& PO<T>::one(){ST CO PO<T> o{c_one()};RE o;}TE <TY T> IN CO PO<T>& PO<T>::x(){ST CO PO<T> f{1,c_one()};RE f;}TE <TY T> IN CO T& PO<T>::c_zero(){ST CO T z{0};RE z;}TE <TY T> IN CO T& PO<T>::c_one(){ST CO T o{1};RE o;}TE <TY T> IN CO T& PO<T>::c_minus_one(){ST CO T m{-1};RE m;}TE <TY T>PO<T> Differential(CRI n,CO PO<T>& f){CRI SZ = f.SZ();if(SZ < n){RE PO<T>::zero();}VE<T> df(SZ - n);T coef = T::Factorial(n);int i = n;WH(i < SZ){df[i - n]= f[i]* coef;i++;(coef *= i)/=(i - n);}RE PO<T>(MO(df));}
TE <TY T>PO<T> PO<T>::NaiveCN(PO<T> f0,CRI valuation0,CO PO<T>& f1,CRI valuation1,CRI N_trunc){CO int SZ0 = f0.SZ();AS(0 <= valuation0 && valuation0 < SZ0);CO int SZ1 = f1.SZ();AS(0 <= valuation1 && valuation1 < SZ1);CO int i_ulim = min(SZ0,N_trunc - valuation1);for(int i = i_ulim - 1;i >= valuation0;i--){CO T f0i = f0[i];f0[i]*= f1[0];CO int j_ulim = min(SZ1,N_trunc - i),j_min = max(valuation1,1);for(int j = j_ulim - 1;j >= j_min;j--){f0[i+j]+= f0i * f1[j];}}RE MO(f0);}TE <TY T,CL Traits> IN OS& OP<<(OS& os,CO PO<T>& f){auto& SZ = f.SZ();for(int i = 0;i < SZ;i++){(i == 0?os:os << " ")<< f[i];}RE os;}
// 特殊化で不使用
TE <TY T>PO<T> PO<T>::NaiveQuotient(PO<T> f0,CO PO<T>& f1){CO int diff = f0.m_SZ - f1.m_SZ;if(diff < 0){RE MO(f0);}CO T r = f0[f0.m_SZ-1]/ f1[f1.m_SZ-1];f0.m_f.pop_back();f0.m_SZ--;f0.Reduce();for(int i = diff;i < f0.m_SZ;i++){f0[i]-= r * f1[i - diff];}f0.Reduce();f0 = NaiveQuotient(MO(f0),f1);f0[diff]= r;RE MO(f0);}TE <TY T>PO<T> PO<T>::NaiveResidue(PO<T> f0,CO PO<T>& f1){CO int diff = f0.m_SZ - f1.m_SZ;if(diff < 0){RE MO(f0);}CO T r = f0[f0.m_SZ-1]/ f1[f1.m_SZ-1];f0.m_f.pop_back();f0.m_SZ--;f0.Reduce();for(int i = diff;i < f0.m_SZ;i++){f0[i]-= r * f1[i - diff];}f0.Reduce();RE NaiveResidue(MO(f0),f1);}TE <TY T>PO<T>& PO<T>::OP*=(PO<T> f){Reduce();if(m_SZ == 0){RE *TH;}f.Reduce();if(f.m_SZ == 0){RE *TH = MO(f);}CO int valuation0 = TH->Valuation();CO int valuation1 = f.Valuation();CO int le0 = m_SZ - valuation0;CO int le1 = f.m_SZ - valuation1;CO int SZ = m_SZ + f.m_SZ - 1;m_f = NaiveCN(MO(*TH),valuation0,f,valuation1,SZ);m_SZ = m_f.SZ();RE *TH;}TE <TY T>PO<T>& PO<T>::OP/=(CO PO<T>& f){AS(f.m_SZ > 0 && f[f.m_SZ-1]!= c_zero());Reduce();if(m_SZ < f.m_SZ){RE *TH = zero();}RE *TH = NaiveQuotient(MO(*TH),f);}TE <TY T>PO<T>& PO<T>::OP%=(CO PO<T>& f){AS(f.m_SZ > 0 && f[f.m_SZ-1]!= c_zero());Reduce();RE *TH = NaiveResidue(MO(*TH),f);}
#endif

/* AAA 常設でないライブラリは以上に挿入する。*/

#define INCLUDE_SUB
#include __FILE__
#else /* INCLUDE_LIBRARY */
#ifdef DEBUG
  #define _GLIBCXX_DEBUG
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize ( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define DEXPR( LL , BOUND , VALUE1 , VALUE2 ) CEXPR( LL , BOUND , VALUE1 )
  #define ASSERT( A , MIN , MAX ) AS( ( MIN ) <= A && A <= ( MAX ) )
  #define REPEAT_MAIN( BOUND ) START_MAIN; CEXPR( int , test_case_num_bound , BOUND ); int test_case_num = 1; if CE( test_case_num_bound > 1 ){ FINISH_MAIN
  #ifdef USE_GETLINE
    #define SET_SEPARATE( SEPARATOR , ... ) VariadicGetline( cin , SEPARATOR , __VA_ARGS__ )
    #define SET( ... ) SET_SEPARATE( '\n' , __VA_ARGS__ )
    #define GETLINE_SEPARATE( SEPARATOR , ... ) string __VA_ARGS__; SET_SEPARATE( SEPARATOR , __VA_ARGS__ )
    #define GETLINE( ... ) GETLINE_SEPARATE( '\n' , __VA_ARGS__ )
    #define FINISH_MAIN GETLINE( test_case_num_str ); test_case_num = stoi( test_case_num_str ); ASSERT( test_case_num , 1 , test_case_num_bound ); } REPEAT( test_case_num ){ Solve(); } }
  #else
    #define SET( ... ) VariadicCin( cin , __VA_ARGS__ )
    #define CIN( LL , ... ) LL __VA_ARGS__; SET( __VA_ARGS__ )
    #define SET_A( I , N , ... ) VariadicResize( N + I , __VA_ARGS__ ); FOR( VARIABLE_FOR_SET_A , 0 , N ){ VariadicSet( cin , VARIABLE_FOR_SET_A + I , __VA_ARGS__ ); }
    #define CIN_A( LL , I , N , ... ) VE<LL> __VA_ARGS__; SET_A( I , N , __VA_ARGS__ )
    #define CIN_AA( LL , I0 , N0 , I1 , N1 , VAR ) VE VAR( N0 + I0 , VE<LL>( N1 + I1 ) ); FOR( VARIABLE_FOR_CIN_AA , 0 , N0 ){ SET_A( I1 , N1 , VAR[VARIABLE_FOR_CIN_AA + I0] ); }
    #define FINISH_MAIN SET_ASSERT( test_case_num , 1 , test_case_num_bound ); } REPEAT( test_case_num ){ Solve(); } }
  #endif
  #define SET_ASSERT( A , MIN , MAX ) SET( A ); ASSERT( A , MIN , MAX )
  #define SOLVE_ONLY 
  #define COUT( ... ) VariadicCout( cout , __VA_ARGS__ ) << ENDL
  #define COUTNS( ... ) VariadicCoutNonSep( cout , __VA_ARGS__ )
  #define CERR( ... ) 
  #define CERRNS( ... ) 
  #define COUT_A( I , N , A ) CoutArray( cout , I , N , A ) << ENDL
  #define CERR_A( I , N , A ) 
  #define WHAT( ... ) 
  #define TLE( CONDITION ) if( !( CONDITION ) ){ ll TLE_VAR = 1; while( TLE_VAR != 0 ){ ( TLE_VAR += 2 ) %= int( 1e9 ); } cerr << TLE_VAR << endl; }
  #define MLE( CONDITION ) if( !( CONDITION ) ){ vector<vector<ll>> MLE_VAR{}; REPEAT( 1e6 ){ MLE_VAR.push_back( vector<ll>( 1e6 ) ); } cerr << MLE_VAR << endl; }
  #define OLE( CONDITION ) if( !( CONDITION ) ){ REPEAT( 1e8 ){ cerr << "OLE\n"; } }
#endif
#ifdef REACTIVE
  #ifndef DEBUG
    #define LOCAL( ... ) 
    #define RSET( A , ... ) SET( A )
  #endif
  #define RCIN( LL , A , ... ) LL A; RSET( A , __VA_ARGS__ )
  #define ENDL endl
#else
  #define ENDL "\n"
#endif
#include <bits/stdc++.h>
using namespace std;
#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define START_MAIN int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define START_WATCH chrono::system_clock::time_point watch = chrono::system_clock::now(); double loop_average_time = 0.0 , loop_start_time = loop_average_time , current_time = loop_start_time; int loop_count = current_time; assert( loop_count == 0 )
#define CURRENT_TIME ( current_time = static_cast<double>( chrono::duration_cast<chrono::microseconds>( chrono::system_clock::now() - watch ).count() / 1000.0 ) )
#define CHECK_WATCH( TL_MS ) ( CURRENT_TIME , loop_count == 0 ? loop_start_time = current_time : loop_average_time = ( current_time - loop_start_time ) / loop_count , ++loop_count , current_time < TL_MS - loop_average_time * 2 - 100.0 )
#define CEXPR( LL , BOUND , VALUE ) CE LL BOUND = VALUE
#define SET_A_ASSERT( I , N , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_A , 0 , N ){ SET_ASSERT( A[VARIABLE_FOR_SET_A + I] , MIN , MAX ); }
#define SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) FOR( VARIABLE_FOR_SET_AA0 , 0 , N0 ){ FOR( VARIABLE_FOR_SET_AA1 , 0 , N1 ){ SET_ASSERT( A[VARIABLE_FOR_SET_AA0 + I0][VARIABLE_FOR_SET_AA1 + I1] , MIN , MAX ); } }
#define CIN_ASSERT( A , MIN , MAX ) decldecay_t( MAX ) A; SET_ASSERT( A , MIN , MAX )
#define CIN_A_ASSERT( I , N , A , MIN , MAX ) vector<decldecay_t( MAX )> A( N + I ); SET_A_ASSERT( I , N , A , MIN , MAX )
#define CIN_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX ) vector A( N0 + I0 , vector<decldecay_t( MAX )>( N1 + I1 ) ); SET_AA_ASSERT( I0 , N0 , I1 , N1 , A , MIN , MAX )
#define PR1( A1 , ... ) A1
#define PR2( A1 , A2 , ... ) A2
#define PR3( A1 , A2 , A3 , ... ) A3
#define FOR_( VAR , INITIAL , FINAL , UPPER , COMP , INCR ) for( decldecay_t( UPPER ) VAR = INITIAL ; VAR COMP FINAL ; VAR INCR )
#define FOR( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , PR1( __VA_ARGS__ ) , < , PR3( __VA_ARGS__ , += PR2( __VA_ARGS__ , ? ) , ++ ) )
#define FOREQ( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , PR1( __VA_ARGS__ ) , <= , PR3( __VA_ARGS__ , += PR2( __VA_ARGS__ , ? ) , ++ ) )
#define FOREQINV( VAR , INITIAL , ... ) FOR_( VAR , INITIAL , PR1( __VA_ARGS__ ) , INITIAL , + 1 > , PR3( __VA_ARGS__ , -= PR2( __VA_ARGS__ , ? ) , -- ) )
#define ITR( ARRAY ) auto begin_ ## ARRAY = ARRAY .BE() , itr_ ## ARRAY = begin_ ## ARRAY , end_ ## ARRAY = ARRAY .EN()
#define FOR_ITR( ARRAY ) for( ITR( ARRAY ) , itr = itr_ ## ARRAY ; itr_ ## ARRAY != end_ ## ARRAY ; itr_ ## ARRAY ++ , itr++ )
#define RUN( ARRAY , ... ) for( auto&& __VA_ARGS__ : ARRAY )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define SET_PRECISION( DECIMAL_DIGITS ) cout << fixed << setprecision( DECIMAL_DIGITS ); cerr << fixed << setprecision( DECIMAL_DIGITS )
#define RETURN( ... ) SOLVE_ONLY; COUT( __VA_ARGS__ ); RE
#define COMPARE( ... ) auto naive = Naive( __VA_ARGS__ , false ); auto answer = Answer( __VA_ARGS__ , false ); bool match = naive == answer; CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Naive ==" , naive , match ? "==" : "!=" , answer , "== Answer" ); if( !match ){ CERR( "出力の不一致が検出されました。" ); RE; }
#define CHECK( ... ) auto answer = Answer( __VA_ARGS__ , false ); CERR( "(" , #__VA_ARGS__ , ") == (" , __VA_ARGS__ , ") : Answer == " , answer )

/* 圧縮用 */
#define TE template
#define TY typename
#define US using
#define ST static
#define AS assert
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define LE length
#define PW Power
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&
#define VI virtual 
#define IS basic_istream<char,Traits>
#define OS basic_ostream<char,Traits>
#define ST_AS static_assert
#define reMO_CO remove_const
#define is_COructible_v is_constructible_v
#define rBE rbegin

/* 型のエイリアス */
#define decldecay_t(VAR)decay_t<decltype(VAR)>
TE <TY F,TY...Args> US ret_t = decltype(declval<F>()(declval<Args>()...));
TE <TY T> US inner_t = TY T::type;
US uint = unsigned int;
US ll = long long;
US ull = unsigned long long;
US ld = long double;
US lld = __float128;

/* VVV 常設ライブラリは以下に挿入する。*/
#ifdef DEBUG
  #include "C:/Users/user/Documents/Programming/Contest/Template/Local/a_Body.hpp"
#else
/* Random (1KB)*/
ll GetRand(CRL Rand_min,CRL Rand_max){AS(Rand_min <= Rand_max);ll AN = time(NULL);RE AN * rand()%(Rand_max + 1 - Rand_min)+ Rand_min;}

/* Set (2KB)*/
#define DC_OF_HASH(...)struct hash<__VA_ARGS__>{IN size_t OP()(CO __VA_ARGS__& n)CO;};
CL is_ordered{PU:is_ordered()= delete;TE <TY T> ST CE auto Check(CO T& t)-> decltype(t < t,true_type());ST CE false_type Check(...);TE <TY T> ST CE CO bool value = is_same_v< decltype(Check(declval<T>())),true_type >;};
TE <TY T>US Set = conditional_t<is_COructible_v<unordered_set<T>>,unordered_set<T>,conditional_t<is_ordered::value<T>,set<T>,VO>>;

#define DF_OF_POP_FOR_SET(SET)TE <TY T> IN T pop_max(SET& S){AS(!S.empty());auto IT = --S.EN();T AN = *IT;S.erase(IT);RE AN;}TE <TY T> IN T pop_min(SET& S){AS(!S.empty());auto IT = S.BE();T AN = *IT;S.erase(IT);RE AN;}TE <TY T> IN SET& OP<<=(SET& S,T t){S.insert(MO(t));RE S;}TE <TY T,TY U> IN SET& OP<<=(SET& S,U&& u){S.insert(T{forward<U>(u)});RE S;}TE <TY T> IN SET& OP>>=(SET& S,CO T& t){auto IT = S.find(t);if(IT != S.EN()){S.erase(IT);}RE S;}TE <TY T,TY U> IN SET& OP>>=(SET& S,CO U& u){RE S >>= T{u};}TE <TY T> IN CO T& Get(CO SET& S,int i){auto BE = S.BE(),EN = S.EN();auto& IT = i < 0?(++i,--EN):BE;WH(i > 0 && IT != EN){--i;++IT;}WH(i < 0 && IT != BE){++i;--IT;}AS(i == 0);RE *IT;}
#define DF_OF_UNION_FOR_SET(SET)TE <TY T> IN SET& OP|=(SET& S0,SET S1){S0.merge(MO(S1));RE S0;}TE <TY T> IN SET OP|(SET S0,SET S1){RE MO(S0.SZ()< S1.SZ()?S1 |= MO(S0):S0 |= MO(S1));}
TE <TY SET,TY T> IN TY SET::const_iterator MaximumLeq(CO SET& S,CO T& t){auto IT = S.upper_bound(t);RE IT == S.BE()?S.EN():--IT;}TE <TY SET,TY T> IN TY SET::const_iterator MaximumLt(CO SET& S,CO T& t){auto IT = S.lower_bound(t);RE IT == S.BE()?S.EN():--IT;}TE <TY SET,TY T> IN TY SET::const_iterator MinimumGeq(CO SET& S,CO T& t){RE S.lower_bound(t);}TE <TY SET,TY T> IN TY SET::const_iterator MinimumGt(CO SET& S,CO T& t){RE S.upper_bound(t);}TE <TY SET,TY ITERATOR> IN VO EraseBack(SET& S,ITERATOR& IT){IT = S.erase(IT);}TE <TY SET,TY ITERATOR> IN VO EraseFront(SET& S,ITERATOR& IT){IT = S.erase(IT);IT == S.BE()?IT = S.EN():--IT;}TE <TE <TY...> TY SET,TY T,TY...Args> IN bool In(CO T& t,CO SET<T,Args...>& S){RE S.count(t)== 1;}DF_OF_POP_FOR_SET(set<T>);DF_OF_POP_FOR_SET(unordered_set<T>);DF_OF_POP_FOR_SET(multiset<T>);DF_OF_POP_FOR_SET(unordered_multiset<T>);DF_OF_UNION_FOR_SET(set<T>);DF_OF_UNION_FOR_SET(unordered_set<T>);DF_OF_UNION_FOR_SET(multiset<T>);DF_OF_UNION_FOR_SET(unordered_multiset<T>);DF_OF_UNION_FOR_SET(VE<T>);DF_OF_UNION_FOR_SET(LI<T>);

/* Tuple (6KB)*/
#define DF_OF_AR_FOR_TUPLE(OPR)TE <TY T,TY U,TE <TY...> TY PAIR> IN auto OP OPR ## =(PAIR<T,U>& t0,CO PAIR<T,U>& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);RE t0;}TE <TY T,TY U,TY V,TE <TY...> TY TUPLE> IN auto OP OPR ## =(TUPLE<T,U,V>& t0,CO TUPLE<T,U,V>& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);RE t0;}TE <TY T,TY U,TY V,TY W,TE <TY...> TY TUPLE> IN auto OP OPR ## =(TUPLE<T,U,V,W>& t0,CO TUPLE<T,U,V,W>& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = get<0>(t1);get<1>(t0)OPR ## = get<1>(t1);get<2>(t0)OPR ## = get<2>(t1);get<3>(t0)OPR ## = get<3>(t1);RE t0;}TE <TY ARG,TY T,TY U,TE <TY...> TY PAIR> IN auto OP OPR ## =(PAIR<T,U>& t0,CO ARG& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;RE t0;}TE <TY ARG,TY T,TY U,TY V,TE <TY...> TY TUPLE> IN auto OP OPR ## =(TUPLE<T,U,V>& t0,CO ARG& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;RE t0;}TE <TY ARG,TY T,TY U,TY V,TY W,TE <TY...> TY TUPLE> IN auto OP OPR ## =(TUPLE<T,U,V,W>& t0,CO ARG& t1)-> decltype((get<0>(t0),t0))&{get<0>(t0)OPR ## = t1;get<1>(t0)OPR ## = t1;get<2>(t0)OPR ## = t1;get<3>(t0)OPR ## = t1;RE t0;}TE <TE <TY...> TY TUPLE,TY...ARGS,TY ARG> IN auto OP OPR(CO TUPLE<ARGS...>& t0,CO ARG& t1)-> decldecay_t((get<0>(t0),t0)){auto t = t0;RE MO(t OPR ## = t1);}
#define DF_OF_INCREMENT_FOR_TUPLE(INCR)TE <TY T,TY U,TE <TY...> TY PAIR> IN auto OP INCR(PAIR<T,U>& t)-> decltype((get<0>(t),t))&{INCR get<0>(t);INCR get<1>(t);RE t;}TE <TY T,TY U,TY V,TE <TY...> TY TUPLE> IN auto OP INCR(TUPLE<T,U,V>& t)-> decltype((get<0>(t),t))&{INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);RE t;}TE <TY T,TY U,TY V,TY W,TE <TY...> TY TUPLE> IN auto OP INCR(TUPLE<T,U,V,W>& t)-> decltype((get<0>(t),t))&{INCR get<0>(t);INCR get<1>(t);INCR get<2>(t);INCR get<3>(t);RE t;}
TE <CL Traits,TY T> IN IS& OP>>(IS& is,tuple<T>& arg){RE is >> get<0>(arg);}TE <CL Traits,TY T,TY U,TE <TY...> TY V> IN auto OP>>(IS& is,V<T,U>& arg)-> decltype((get<0>(arg),is))&{RE is >> get<0>(arg)>> get<1>(arg);}TE <CL Traits,TY T,TY U,TY V> IN IS& OP>>(IS& is,tuple<T,U,V>& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg);}TE <CL Traits,TY T,TY U,TY V,TY W> IN IS& OP>>(IS& is,tuple<T,U,V,W>& arg){RE is >> get<0>(arg)>> get<1>(arg)>> get<2>(arg)>> get<3>(arg);}TE <CL Traits,TY T> IN OS& OP<<(OS& os,CO tuple<T>& arg){RE os << get<0>(arg);}TE <CL Traits,TY T,TY U,TE <TY...> TY V> IN auto OP<<(OS& os,CO V<T,U>& arg)-> decltype((get<0>(arg),os))&{RE os << get<0>(arg)<< " " << get<1>(arg);}TE <CL Traits,TY T,TY U,TY V> IN OS& OP<<(OS& os,CO tuple<T,U,V>& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg);}TE <CL Traits,TY T,TY U,TY V,TY W> IN OS& OP<<(OS& os,CO tuple<T,U,V,W>& arg){RE os << get<0>(arg)<< " " << get<1>(arg)<< " " << get<2>(arg)<< " " << get<3>(arg);}DF_OF_AR_FOR_TUPLE(+);TE <TY T,TY U,TE <TY...> TY V> IN auto OP-(CO V<T,U>& t)-> decldecay_t((get<0>(t),t)){RE{-get<0>(t),-get<1>(t)};}TE <TY T,TY U,TY V> IN tuple<T,U,V> OP-(CO tuple<T,U,V>& t){RE{-get<0>(t),-get<1>(t),-get<2>(t)};}TE <TY T,TY U,TY V,TY W> IN tuple<T,U,V,W> OP-(CO tuple<T,U,V,W>& t){RE{-get<0>(t),-get<1>(t),-get<2>(t),-get<3>(t)};}DF_OF_AR_FOR_TUPLE(-);DF_OF_AR_FOR_TUPLE(*);DF_OF_AR_FOR_TUPLE(/);DF_OF_AR_FOR_TUPLE(%);DF_OF_INCREMENT_FOR_TUPLE(++);DF_OF_INCREMENT_FOR_TUPLE(--);

TE <int n>CL TupleAccessIndex{};TE <TY...Types>CL Tuple:PU tuple<Types...>{PU:IN Tuple(Types&&... args);TE <TY...Args> IN Tuple(Args&&... args);TE <int n> IN auto& OP[](CO TupleAccessIndex<n>& i)NE;TE <int n> IN CO auto& OP[](CO TupleAccessIndex<n>& i)CO NE;};TE <TY...Types>CL tuple_size<Tuple<Types...>>:PU tuple_size<tuple<Types...>>{};TE <size_t n,TY...Types>CL tuple_element<n,Tuple<Types...>>:PU tuple_element<n,tuple<Types...>>{};
TE <TY T,TY U> US Pair = Tuple<T,U>;TE <TY INT> US T2 = Pair<INT,INT>;TE <TY INT> US T3 = Tuple<INT,INT,INT>;TE <TY INT> US T4 = Tuple<INT,INT,INT,INT>;
CE TupleAccessIndex<0> O{};CE TupleAccessIndex<1> I{};CE TupleAccessIndex<2> II{};CE TupleAccessIndex<3> III{};
TE <TY...Types> IN Tuple<Types...>::Tuple(Types&&... args):tuple<Types...>(MO(args)...){}TE <TY...Types> TE <TY...Args> IN Tuple<Types...>::Tuple(Args&&... args):tuple<Types...>(forward<Args>(args)...){}TE <TY...Types> TE <int n> IN auto& Tuple<Types...>::OP[](CO TupleAccessIndex<n>& i)NE{RE get<n>(*TH);}TE <TY...Types> TE <int n> IN CO auto& Tuple<Types...>::OP[](CO TupleAccessIndex<n>& i)CO NE{RE get<n>(*TH);}TE <TY RET,TE <TY...> TY PAIR,TY INT> T2<RET> cast(CO PAIR<INT,INT>& t){RE{get<0>(t),get<1>(t)};}TE <TY RET,TY INT> T3<RET> cast(CO tuple<INT,INT,INT>& t){RE{get<0>(t),get<1>(t),get<2>(t)};}TE <TY RET,TY INT> T4<RET> cast(CO tuple<INT,INT,INT,INT>& t){RE{get<0>(t),get<1>(t),get<2>(t),get<3>(t)};}

#define DF_OF_HASH_FOR_TUPLE(PAIR)TE <TY T,TY U> IN size_t hash<PAIR<T,U>>::OP()(CO PAIR<T,U>& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash<T> h0;ST CO hash<U> h1;RE(h0(get<0>(n))* seed)^ h1(get<1>(n));}
TE <TY T> DC_OF_HASH(tuple<T>);TE <TY T,TY U> DC_OF_HASH(pair<T,U>);TE <TY T,TY U> DC_OF_HASH(tuple<T,U>);TE <TY T,TY U,TY V> DC_OF_HASH(tuple<T,U,V>);TE <TY T,TY U,TY V,TY W> DC_OF_HASH(tuple<T,U,V,W>);
TE <TY T> IN size_t hash<tuple<T>>::OP()(CO tuple<T>& n)CO{ST CO hash<T> h;RE h(get<0>(n));}DF_OF_HASH_FOR_TUPLE(pair);DF_OF_HASH_FOR_TUPLE(tuple);TE <TY T,TY U,TY V> IN size_t hash<tuple<T,U,V>>::OP()(CO tuple<T,U,V>& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash<pair<T,U>> h01;ST CO hash<V> h2;RE(h01({get<0>(n),get<1>(n)})* seed)^ h2(get<2>(n));}TE <TY T,TY U,TY V,TY W> IN size_t hash<tuple<T,U,V,W>>::OP()(CO tuple<T,U,V,W>& n)CO{ST CO size_t seed =(GetRand(1e3,1e8)<< 1)| 1;ST CO hash<pair<T,U>> h01;ST CO hash<pair<V,W>> h23;RE(h01({get<0>(n),get<1>(n)})* seed)^ h23({get<2>(n),get<3>(n)});}

/* Vector (3KB)*/
#define DF_OF_COUT_FOR_VE(V)TE <CL Traits,TY Arg> IN OS& OP<<(OS& os,CO V<Arg>& arg){auto BE = arg.BE(),EN = arg.EN();auto IT = BE;WH(IT != EN){(IT == BE?os:os << " ")<< *IT;IT++;}RE os;}
DF_OF_COUT_FOR_VE(VE);DF_OF_COUT_FOR_VE(LI);DF_OF_COUT_FOR_VE(set);DF_OF_COUT_FOR_VE(unordered_set);DF_OF_COUT_FOR_VE(multiset);IN VO VariadicResize(CRI SZ){}TE <TY Arg,TY... ARGS> IN VO VariadicResize(CRI SZ,Arg& arg,ARGS&... args){arg.resize(SZ);VariadicResize(SZ,args...);}

#define DF_OF_AR_FOR_VE(V,OPR)TE <TY T> IN V<T>& OP OPR ## =(V<T>& a0,CO V<T>& a1){AS(a0.SZ()<= a1.SZ());auto IT0 = a0.BE(),EN0 = a0.EN();auto IT1 = a1.BE();WH(IT0 != EN0){*(IT0++)OPR ## = *(IT1++);}RE a0;}TE <TY T> IN V<T>& OP OPR ## =(V<T>& a,CO T& t){for(auto& x:a){x OPR## = t;}RE a;}TE <TY T,TY U> IN V<T> OP OPR(V<T> a,CO U& u){RE MO(a OPR ## = u);}
#define DF_OF_INCREMENT_FOR_VE(V,INCR)TE <TY T> IN V<T>& OP INCR(V<T>& a){for(auto& i:a){INCR i;}RE a;}
#define DF_OF_SHIFT_FOR_VE(V)TE <TY T> IN V<T>& OP<<=(V<T>& a,T t){a.push_back(MO(t));RE a;}TE <TY T,TY U> IN V<T>& OP<<=(V<T>& a,U&& u){RE a <<= T{forward<U>(u)};}TE <TY T> IN T pop(V<T>& a){AS(!a.empty());T AN = MO(a.back());a.pop_back();RE AN;}
#define DF_OF_ARS_FOR_VE(V)DF_OF_AR_FOR_VE(V,+);DF_OF_AR_FOR_VE(V,-);DF_OF_AR_FOR_VE(V,*);DF_OF_AR_FOR_VE(V,/);DF_OF_AR_FOR_VE(V,%);DF_OF_INCREMENT_FOR_VE(V,++);DF_OF_INCREMENT_FOR_VE(V,--);TE <TY T> IN V<T> OP-(V<T> a){RE MO(a *= T(-1));}TE <TY T> IN V<T> OP*(CO T& t,V<T> v){RE MO(v *= t);}DF_OF_SHIFT_FOR_VE(V);
DF_OF_ARS_FOR_VE(VE);DF_OF_ARS_FOR_VE(LI);DF_OF_SHIFT_FOR_VE(basic_string);
TE <TY V> IN auto Get(V& a){RE[&](CRI i = 0)-> CO decldecay_t(a[0])&{RE a[i];};}TE <TY T> IN VE<T> id(CRI SZ){VE<T> AN(SZ);for(int i = 0;i < SZ;i++){AN[i]= i;}RE AN;}TE <TY V> IN VO Sort(V& a,CO bool& reversed = false){US T = decldecay_t(a[0]);if(reversed){ST auto comp =[](CO T& t0,CO T& t1){RE t1 < t0;};sort(a.BE(),a.EN(),comp);}else{sort(a.BE(),a.EN());}}TE <TY V0,TY V1> IN VO Sort(V0& a,V1& b,CO bool& reversed = false){CO int SZ = a.SZ();AS(SZ == int(b.SZ()));VE<pair<decldecay_t(a[0]),decldecay_t(b[0])>> v(SZ);for(int i = 0;i < SZ;i++){v[i]={MO(a[i]),MO(b[i])};}Sort(v,reversed);for(int i = 0;i < SZ;i++){a[i]= MO(v[i].first);b[i]= MO(v[i].second);}}TE <TY V> IN pair<VE<int>,VE<int>> IndexSort(CO V& a,CO bool& reversed = false){CO int SZ = a.SZ();auto index = id<int>(SZ),ord = index;sort(index.BE(),index.EN(),[&](CRI i,CRI j){CO pair ti{a[i],i},tj{a[j],j};RE reversed?tj < ti:ti < tj;});for(int i = 0;i < SZ;i++){ord[index[i]]= i;}RE{MO(index),MO(ord)};}TE <TY V> IN int len(CO V& a){RE a.SZ();}TE <TY V> IN VO Reverse(V& a){CO int SZ = len(a),half = SZ / 2;for(int i = 0;i < half;i++){swap(a[i],a[SZ-1-i]);}};TE <TY V> IN V Reversed(V a){Reverse(a);RE MO(a);}TE <TY RET,TE <TY...> TY V,TY T> IN V<RET> cast(CO V<T>& a){V<RET> AN{};for(auto& x:a){AN <<= a;}}

/* Map (1KB)*/
#define DF_OF_AR_FOR_MAP(MAP,OPR)TE <TY T,TY U> IN MAP<T,U>& OP OPR ## =(MAP<T,U>& a,CO pair<T,U>& v){a[v.first]OPR ## = v.second;RE a;}TE <TY T,TY U> IN MAP<T,U>& OP OPR ## =(MAP<T,U>& a0,CO MAP<T,U>& a1){for(auto&[t,u]:a1){a0[t]OPR ## = u;}RE a0;}TE <TY T,TY U,TY ARG> IN MAP<T,U> OP OPR(MAP<T,U> a,CO ARG& arg){RE MO(a OPR ## = arg);}
#define DF_OF_ARS_FOR_MAP(MAP)DF_OF_AR_FOR_MAP(MAP,+);DF_OF_AR_FOR_MAP(MAP,-);DF_OF_AR_FOR_MAP(MAP,*);DF_OF_AR_FOR_MAP(MAP,/);DF_OF_AR_FOR_MAP(MAP,%);
TE <TY T,TY U>US Map = conditional_t<is_COructible_v<unordered_map<T,int>>,unordered_map<T,U>,conditional_t<is_ordered::value<T>,map<T,U>,VO>>;
DF_OF_ARS_FOR_MAP(map);DF_OF_ARS_FOR_MAP(unordered_map);

/* StdStream (2KB)*/
TE <CL Traits> IN IS& VariadicCin(IS& is){RE is;}TE <CL Traits,TY Arg,TY... ARGS> IN IS& VariadicCin(IS& is,Arg& arg,ARGS&... args){RE VariadicCin(is >> arg,args...);}TE <CL Traits> IN IS& VariadicSet(IS& is,CRI i){RE is;}TE <CL Traits,TY Arg,TY... ARGS> IN IS& VariadicSet(IS& is,CRI i,Arg& arg,ARGS&... args){RE VariadicSet(is >> arg[i],i,args...);}TE <CL Traits> IN IS& VariadicGetline(IS& is,CO char& separator){RE is;}TE <CL Traits,TY Arg,TY... ARGS> IN IS& VariadicGetline(IS& is,CO char& separator,Arg& arg,ARGS&... args){RE VariadicGetline(getline(is,arg,separator),separator,args...);}TE <CL Traits,TY Arg> IN OS& VariadicCout(OS& os,Arg&& arg){RE os << forward<Arg>(arg);}TE <CL Traits,TY Arg1,TY Arg2,TY... ARGS> IN OS& VariadicCout(OS& os,Arg1&& arg1,Arg2&& arg2,ARGS&&... args){RE VariadicCout(os << forward<Arg1>(arg1)<< " ",forward<Arg2>(arg2),forward<ARGS>(args)...);}TE <CL Traits,TY Arg> IN OS& VariadicCoutNonSep(OS& os,Arg&& arg){RE os << forward<Arg>(arg);}TE <CL Traits,TY Arg1,TY Arg2,TY... ARGS> IN OS& VariadicCoutNonSep(OS& os,Arg1&& arg1,Arg2&& arg2,ARGS&&... args){RE VariadicCoutNonSep(os << forward<Arg1>(arg1),forward<Arg2>(arg2),forward<ARGS>(args)...);}TE <CL Traits,TY ARRAY> IN OS& CoutArray(OS& os,CRI i_start,CRI i_ulim,ARRAY&& a){for(int i = i_start;i < i_ulim;i++){(i == i_start?os:(os << " "))<< a[i];}RE os;}

/* Iteration (3KB) */
#define SPECIALSATION_OF_AR_PROGRESSION_SUM(TYPE)TE <> IN TYPE ArithmeticProgressionSum(CO TYPE& l,CO TYPE& r,CO TYPE& d){RE SpecialisedArithmeticProgressionSum(l,r,d);}
 TE <TY T,TY U,TE <TY...> TY V,TY OPR> T LeftConnectiveProd(T t,CO V<U>& f,OPR opr){for(auto& u:f){t = opr(MO(t),u);}RE MO(t);}TE <TY T,TY U,TE <TY...> TY V> IN T Sum(CO V<U>& f){RE LeftConnectiveProd(T{0},f,[](T t0,CO U& u1){RE MO(t0 += u1);});}TE <TY T,TY U,TE <TY...> TY V> IN T Prod(CO V<U>& f){RE LeftConnectiveProd(T{1},f,[](T t0,CO U& u1){RE MO(t0 *= u1);});}TE <TY T> IN T& SetMax(T& t){RE t;}TE <TY T,TY U,TY... Args> IN T& SetMax(T& t0,CO U& u1,CO Args&... args){RE SetMax(t0 < u1?t0 = u1:t0,args...);}TE <TY T> IN T& SetMin(T& t){RE t;}TE <TY T,TY U,TY... Args> IN T& SetMin(T& t0,CO U& u1,CO Args&... args){RE SetMin(u1 < t0?t0 = u1:t0,args...);}TE <TY T> IN CO T& Max(CO VE<T>& f){RE *max_element(f.BE(),f.EN());}TE <TY T,TE <TY...> TY SET> IN CO T& Max(CO SET<T>& f){RE *--f.EN();}TE <TY T,TY U,TY...Args> IN T Max(T t0,CO U& t1,CO Args&... args){RE MO(SetMax(t0,t1,args...));}TE <TY T> IN CO T& Min(CO VE<T>& f){RE *min_element(f.BE(),f.EN());}TE <TY T,TE <TY...> TY SET> IN CO T& Min(CO SET<T>& f){RE *f.BE();}TE <TY T,TY U,TY...Args> IN T Min(T t0,CO U& t1,CO Args&... args){RE MO(SetMin(t0,t1,args...));}TE <TY T,TY UINT>T Power(CO T& t,CO UINT& EX,T init = 1){RE EX > 1?Power(t * t,EX >> 1,MO(EX & 1?init *= t:init)):MO(EX > 0?init *= t:(AS(EX == 0),init));}TE <TY T> IN T PowerMemorisation(CO T& t,CRI EX){AS(EX >= 0);ST Map<T,VE<T>> memory{};auto& AN = memory[t];if(AN.empty()){AN.push_back(1);}WH(int(AN.SZ())<= EX){AN.push_back(AN.back()* t);}RE AN[EX];}TE <TY INT> IN INT ArithmeticProgressionSum(CO INT& l,CO INT& r,CO INT& d = 1){RE(l + r)*(r - l + 1)/ 2;}TE <TY INT> IN INT SpecialisedArithmeticProgressionSum(CO INT& l,CO INT& r,CO INT& d){AS(l - 1 <= r);CO INT c =(r - l)/ d;RE l - 1 == r?0:(c & 1)== 0?(c + 1)*(l + d *(c >> 1)):((c + 1)>> 1)*((l << 1)+ d * c);}
SPECIALSATION_OF_AR_PROGRESSION_SUM(int);
SPECIALSATION_OF_AR_PROGRESSION_SUM(uint);
SPECIALSATION_OF_AR_PROGRESSION_SUM(ll);
SPECIALSATION_OF_AR_PROGRESSION_SUM(ull);
TE <TY INT> IN INT ArithmeticProgressionSum(CO INT& r){RE ArithmeticProgressionSum(INT{},r);}TE <TY T,TY UINT> IN T GeometricProgressionSum(T rate,UINT EX_max,CO T& init = 1){T rate_minus = rate - 1;RE rate_minus == 0?init * ++EX_max:(Power(MO(rate),MO(++EX_max))- 1)/ MO(rate_minus)* init;}TE <TY T,TY UINT>T GeometricProgressionLinearCombinationSum(VE<T> rate,VE<UINT> EX_max,CO VE<T>& init){CO int SZ = init.SZ();AS(int(rate.SZ())== SZ && int(EX_max.SZ())== SZ);T AN{};for(int i = 0;i < SZ;i++){AN += GeometricProgressionSum(MO(rate[i]),MO(EX_max[i]),init[i]);}RE AN;}

/* Sqrt (1KB) */
TE <TY INT>INT RoundDownSqrt(CO INT& n){ST_AS(is_same_v<INT,int> || is_same_v<INT,uint> || is_same_v<INT,ll> || is_same_v<INT,ull>);AS(n >= 0);if(n <= 1){RE n;}CE INT r_max = is_same_v<INT,int>?46341:is_same_v<INT,uint>?65536:is_same_v<INT,ll>?3037000500:4294967296;INT l = 1,r = min(r_max,n);WH(l < r - 1){CO INT m =(l + r)>> 1;(m <= n / m?l:r)= m;}RE l;}TE <TY INT>INT RoundUpSqrt(CO INT& n){ST_AS(is_same_v<INT,int> || is_same_v<INT,uint> || is_same_v<INT,ll> || is_same_v<INT,ull>);AS(n >= 0);if(n <= 2){RE n;}CE INT r_max = is_same_v<INT,int>?46341:is_same_v<INT,uint>?65536:is_same_v<INT,ll>?3037000500:4294967296;CO INT n_minus = n - 1;INT l = 1,r = min(r_max,n);WH(l + 1 < r){CO INT m =(l + r)>> 1;(m <= n_minus / m?l:r)= m;}RE r;}TE <TY INT> bool IsSquare(CO INT& n){CO INT r = RoundDownSqrt(n);RE n == r * r;}

/* Loop (1KB)*/
TE <TY INT> bool NextLoop(CRI SZ,CO VE<INT>& lower_bound,CO VE<INT>& upper_limit,VE<INT>& index){int depth = 0;WH(depth < SZ){if(++index[depth]< upper_limit[depth]){break;}index[depth]= lower_bound[depth];depth++;}RE depth < SZ;}TE <TY INT> bool NextLoop(CO VE<INT>& lower_bound,CO VE<INT>& upper_limit,VE<INT>& index){RE NextLoop(index.SZ(),lower_bound,upper_limit,index);}TE <TY INT> bool NextLoopEq(CRI SZ,CO VE<INT>& lower_bound,CO VE<INT>& upper_bound,VE<INT>& index){int depth = 0;WH(depth < SZ){if(++index[depth]<= upper_bound[depth]){break;}index[depth]= lower_bound[depth];depth++;}RE depth < SZ;}TE <TY INT> bool NextLoopEq(CO VE<INT>& lower_bound,CO VE<INT>& upper_bound,VE<INT>& index){RE NextLoopEq(index.SZ(),lower_bound,upper_bound,index);}

/* string (1KB)*/
TE <TY INT> IN char IntToChar(CO INT& i,CO char& c = 'a'){RE c + i;}TE <TY INT = int> IN INT CharToInt(CO char& i){RE i -(i < 'a'?'A':'a');}TE <TY INT>string ArrayToString(CO VE<INT>& A,CO char& c = 'a'){CO int N = A.SZ();string S(N,c);for(int i = 0;i < N;i++){S[i]= IntToChar<INT>(A[i],c);}RE S;}TE <TY INT = int>VE<INT> StringToArray(CO string& S){CO int N = S.SZ();VE<int> A(N);for(int i = 0;i < N;i++){A[i]= CharToInt<INT>(S[i]);}RE A;}TE <TY INT>string ArrayToParenthesisString(CO VE<INT>& A){CO int N = A.SZ();string S(N,'(');for(int i = 0;i < N;i++){AS(0 <= A[i]&& A[i]<= 1);S[i]= "()"[A[i]];}RE S;}TE <TY INT = int>VE<INT> ParenthesisStringToArray(CO string& S){CO int N = S.SZ();VE<int> A(N);for(int i = 0;i < N;i++){A[i]= S[i]- '(';}RE A;}
#endif
/* AAA 常設ライブラリは以上に挿入する。*/

#define INCLUDE_LIBRARY
#include __FILE__
#endif /* INCLUDE_LIBRARY */
#endif /* INCLUDE_SUB */
#endif /* INCLUDE_MAIN */