#pragma GCC optimize ( "O3" ) #pragma GCC target ( "avx" ) #include using namespace std;using uint = unsigned int;using ll = long long; #define TE template #define TY typename #define ST static #define IN inline #define PU public #define PR PU #define OP operator #define CE constexpr #define CO const #define RE return #define NE noexcept #define WH while #define VE vector #define LI list #define SZ size #define MO move #define C_INT CO int #define C_UINT CO uint& #define CR_UINT CO uint& #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define RETURN( ANSWER ) COUT( ANSWER ); QUIT TE IN T Residue(CO T& a,CO T& p){ RE a >= 0 ? a % p:p - (- a - 1) % p - 1; }TE class Mod{PR:ll m_n;ll m_inv;PU:IN Mod() NE;IN Mod(CO ll& n) NE;IN Mod(CO Mod& n) NE;IN Mod& OP=(CO ll& n) NE;Mod& OP=(CO Mod& n) NE;Mod& OP+=(CO ll& n) NE;IN Mod& OP+=(CO Mod& n) NE;IN Mod& OP-=(CO ll& n) NE;IN Mod& OP-=(CO Mod& n) NE;Mod& OP*=(CO ll& n) NE;Mod& OP*=(CO Mod& n) NE;virtual Mod& OP/=(CO ll& n);virtual Mod& OP/=(CO Mod& n);Mod& OP%=(CO ll& n);IN Mod& OP%=(CO Mod& n);IN Mod OP-() CO NE;IN Mod& OP++() NE;IN Mod& OP++(int) NE;IN Mod& OP--() NE;IN Mod& OP--(int) NE;IN CO ll& Represent() CO NE;void Invert() NE;bool CheckInvertible() NE;bool IsSmallerThan(CO ll& n) CO NE;bool IsBiggerThan(CO ll& n) CO NE;};TE IN bool OP==(CO Mod& n0,CO ll& n1) NE;TE IN bool OP==(CO ll& n0,CO Mod& n1) NE;TE IN bool OP==(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP==(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP!=(CO Mod& n0,CO ll& n1) NE;TE IN bool OP!=(CO ll& n0,CO Mod& n1) NE;TE IN bool OP!=(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP!=(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP<(CO Mod& n0,CO ll& n1) NE;TE IN bool OP<(CO ll& n0,CO Mod& n1) NE;TE IN bool OP<(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP<=(CO Mod& n0,CO ll& n1) NE;TE IN bool OP<=(CO ll& n0,CO Mod& n1) NE;TE IN bool OP<=(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP<=(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP>(CO Mod& n0,CO ll& n1) NE;TE IN bool OP>(CO ll& n0,CO Mod& n1) NE;TE IN bool OP>(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP>(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP>=(CO Mod& n0,CO ll& n1) NE;TE IN bool OP>=(CO ll& n0,CO Mod& n1) NE;TE IN bool OP>=(CO Mod& n0,CO Mod& n1) NE;TE IN bool OP>=(CO Mod& n0,CO Mod& n1) NE;TE Mod OP+(CO Mod& n0,CO ll& n1) NE;TE Mod OP+(CO ll& n0,CO Mod& n1) NE;TE Mod OP+(CO Mod& n0,CO Mod& n1) NE;TE IN Mod OP-(CO Mod& n0,CO ll& n1) NE;TE Mod OP-(CO ll& n0,CO Mod& n1) NE;TE Mod OP-(CO Mod& n0,CO Mod& n1) NE;TE Mod OP*(CO Mod& n0,CO ll& n1) NE;TE Mod OP*(CO ll& n0,CO Mod& n1) NE;TE Mod OP*(CO Mod& n0,CO Mod& n1) NE;TE Mod OP/(CO Mod& n0,CO ll& n1);TE Mod OP/(CO ll& n0,CO Mod& n1);TE Mod OP/(CO Mod& n0,CO Mod& n1);TE Mod OP%(CO Mod& n0,CO ll& n1);TE IN Mod OP%(CO ll& n0,CO Mod& n1);TE IN Mod OP%(CO Mod& n0,CO Mod& n1);TE Mod Inverse(CO Mod& n);TE Mod Power(CO Mod& n,CO ll& p,CO string& method = "normal");TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method);TE IN Mod Power(CO Mod& n,CO Mod& p,CO string& method = "normal");TE <> IN Mod<2> Power(CO Mod<2>& n,CO Mod<2>& p,CO string& method);TE IN T Square(CO T& t);TE <> IN Mod<2> Square >(CO Mod<2>& t);TE IN string to_string(CO Mod& n) NE;TE IN basic_ostream& OP<<(basic_ostream& os,CO Mod& n);void LazyEvaluationOfModularInverse(CO ll& M,CO ll& n,ll& m){CE CO ll border = 1000000;if(n > border){CO ll n_minus = M - n;if(n_minus <= border){LazyEvaluationOfModularInverse(M,n_minus,m);m = M - m;RE;} else {m = 1;ll exponent = M - 2;ll power_n = n;WH(exponent != 0){if(exponent % 2 == 1){(m *= power_n) %= M;}(power_n *= power_n) %= M;exponent /= 2;}RE;}}ST LI memory_M{};ST LI > memory_inverse{};auto I_M = memory_M.begin(),end_M = memory_M.end();auto I_inverse = memory_inverse.begin();VE* p_inverse = nullptr;WH(I_M != end_M && p_inverse == nullptr){if(*I_M == M){p_inverse = &(*I_inverse);}I_M++;I_inverse++;}if(p_inverse == nullptr){memory_M.push_front(M);memory_inverse.push_front(VE());p_inverse = &(memory_inverse.front());p_inverse->push_back(M);}CO ll SZ = p_inverse->SZ();for(ll i = SZ;i <= n;i++){p_inverse->push_back(0);}ll& n_inv = (*p_inverse)[n];if(n_inv != 0){m = n_inv;RE;}CO ll M_abs = M >= 0 ? M:-M;CO ll n_sub = M_abs % n;ll n_sub_inv = (*p_inverse)[n_sub];if(n_sub_inv == 0){LazyEvaluationOfModularInverse(M,n_sub,n_sub_inv);}if(n_sub_inv != M){n_inv = M_abs - ((n_sub_inv * (M_abs / n)) % M_abs);m = n_inv;RE;}for(ll i = 1;i < M_abs;i++){if((n * i) % M_abs == 1){n_inv = i;m = n_inv;RE;}}n_inv = M;m = n_inv;RE;}TE IN Mod::Mod() NE:m_n(0),m_inv(M){}TE IN Mod::Mod(CO ll& n) NE:m_n(Residue(n,M)),m_inv(0){}TE IN Mod::Mod(CO Mod& n) NE:m_n(n.m_n),m_inv(0){}TE IN Mod& Mod::OP=(CO ll& n) NE { RE OP=(Mod(n)); }TE Mod& Mod::OP=(CO Mod& n) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE Mod& Mod::OP+=(CO ll& n) NE{m_n = Residue(m_n + n,M);m_inv = 0;RE *this;}TE IN Mod& Mod::OP+=(CO Mod& n) NE { RE OP+=(n.m_n); };TE IN Mod& Mod::OP-=(CO ll& n) NE { RE OP+=(-n); }TE IN Mod& Mod::OP-=(CO Mod& n) NE { RE OP-=(n.m_n); }TE Mod& Mod::OP*=(CO ll& n) NE{m_n = Residue(m_n * n,M);m_inv = 0;RE *this;}TE Mod& Mod::OP*=(CO Mod& n) NE{m_n = Residue(m_n * n.m_n,M);if(m_inv == 0 || n.m_inv == 0){m_inv = 0;} else if(m_inv == M || n.m_inv == M){m_inv = M;} else {Residue(m_inv * n.m_inv,M);}RE *this;}TE Mod& Mod::OP/=(CO ll& n){RE OP/=(Mod(n));}TE Mod& Mod::OP/=(CO Mod& n){RE OP*=(Inverse(n));}TE Mod& Mod::OP%=(CO ll& n){m_n %= Residue(n,M);m_inv = 0;RE *this;}TE IN Mod& Mod::OP%=(CO Mod& n) { RE OP%=(n.m_n); }TE IN Mod Mod::OP-() CO NE { RE Mod(0).OP-=(*this); }TE IN Mod& Mod::OP++() NE { RE OP+=(1); }TE IN Mod& Mod::OP++(int) NE { RE OP++(); }TE IN Mod& Mod::OP--() NE { RE OP-=(1); }TE IN Mod& Mod::OP--(int) NE { RE OP-=(); }TE IN CO ll& Mod::Represent() CO NE { RE m_n; }TE void Mod::Invert() NE{if(CheckInvertible()){ll i = m_inv;m_inv = m_n;m_n = i;} else {m_n = M;m_inv = M;}RE;}TE bool Mod::CheckInvertible() NE{if(m_inv == 0){LazyEvaluationOfModularInverse(M,m_n,m_inv);}RE m_inv != M;}TE IN bool Mod::IsSmallerThan(CO ll& n) CO NE { RE m_n < Residue(n,M); }TE IN bool Mod::IsBiggerThan(CO ll& n) CO NE { RE m_n > Residue(n,M); }TE IN bool OP==(CO Mod& n0,CO ll& n1) NE { RE n0 == Mod(n1); }TE IN bool OP==(CO ll& n0,CO Mod& n1) NE { RE Mod(n0) == n0; }TE IN bool OP==(CO Mod& n0,CO Mod& n1) NE { RE n0.Represent() == n1.Represent(); }TE IN bool OP!=(CO Mod& n0,CO ll& n1) NE { RE !(n0 == n1); }TE IN bool OP!=(CO ll& n0,CO Mod& n1) NE { RE !(n0 == n1); }TE IN bool OP!=(CO Mod& n0,CO Mod& n1) NE { RE !(n0 == n1); }TE IN bool OP<(CO Mod& n0,CO ll& n1) NE { RE n0.IsSmallerThan(n1); }TE IN bool OP<(CO ll& n0,CO Mod& n1) NE { RE n1.IsBiggerThan(n0); }TE IN bool OP<(CO Mod& n0,CO Mod& n1) NE { RE n0.Represent() < n1.Represent(); }TE IN bool OP<=(CO Mod& n0,CO ll& n1) NE { RE !(n1 < n0); }TE IN bool OP<=(CO ll& n0,CO Mod& n1) NE { RE !(n1 < n0); }TE IN bool OP<=(CO Mod& n0,CO Mod& n1) NE { RE !(n1 < n0); }TE IN bool OP>(CO Mod& n0,CO ll& n1) NE { RE n1 < n0; }TE IN bool OP>(CO ll& n0,CO Mod& n1) NE { RE n1 < n0; }TE IN bool OP>(CO Mod& n0,CO Mod& n1) NE { RE n1 < n0; }TE IN bool OP>=(CO Mod& n0,CO ll& n1) NE { RE !(n0 < n1); }TE IN bool OP>=(CO ll& n0,CO Mod& n1) NE { RE !(n0 < n1); }TE IN bool OP>=(CO Mod& n0,CO Mod& n1) NE { RE !(n0 < n1); }TE Mod OP+(CO Mod& n0,CO ll& n1) NE{auto n = n0;n += n1;RE n;}TE IN Mod OP+(CO ll& n0,CO Mod& n1) NE { RE n1 + n0; }TE IN Mod OP+(CO Mod& n0,CO Mod& n1) NE { RE n0 + n1.Represent(); }TE IN Mod OP-(CO Mod& n0,CO ll& n1) NE { RE n0 + (-n1); }TE IN Mod OP-(CO ll& n0,CO Mod& n1) NE { RE Mod(n0 - n1.Represent()); }TE IN Mod OP-(CO Mod& n0,CO Mod& n1) NE { RE n0 - n1.Represent(); }TE Mod OP*(CO Mod& n0,CO ll& n1) NE{auto n = n0;n *= n1;RE n;}TE IN Mod OP*(CO ll& n0,CO Mod& n1) NE { RE n1 * n0; }TE Mod OP*(CO Mod& n0,CO Mod& n1) NE{auto n = n0;n *= n1;RE n;}TE IN Mod OP/(CO Mod& n0,CO ll& n1) { RE n0 / Mod(n1); }TE IN Mod OP/(CO ll& n0,CO Mod& n1) { RE Mod(n0) / n1; }TE Mod OP/(CO Mod& n0,CO Mod& n1){auto n = n0;n /= n1;RE n;}TE Mod OP%(CO Mod& n0,CO ll& n1){auto n = n0;n %= n1;RE n;}TE IN Mod OP%(CO ll& n0,CO Mod& n1) { RE Mod(n0) % n1.Represent(); }TE IN Mod OP%(CO Mod& n0,CO Mod& n1) { RE n0 % n1.Represent(); }TE Mod Inverse(CO Mod& n){auto n_copy = n;n_copy.Invert();RE n_copy;}TE Mod Power(CO Mod& n,CO ll& p,CO string& method){if(p >= 0){RE Power,ll>(n,p,1,true,true,method);}RE Inverse(Power(n,-p,method));}TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method) { RE p == 0 ? 1:n; }TE IN Mod Power(CO Mod& n,CO Mod& p,CO string& method) { RE Power,ll>(n,p.Represent(),method); }TE <> IN Mod<2> Power(CO Mod<2>& n,CO Mod<2>& p,CO string& method) { RE p == 0 ? 1:n; }TE <> IN Mod<2> Square >(CO Mod<2>& t) { RE t; }TE IN string to_string(CO Mod& n) NE { RE to_string(n.Represent()) + " + MZ"; }TE IN basic_ostream& OP<<(basic_ostream& os,CO Mod& n) { RE os << n.Represent(); } #define RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(CONDITION) if(CONDITION){ RE OP=(zero); } #define RE_ZERO_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL_IF(CONDITION) if(CONDITION){ RE TRPO(m_N); } #define SET_VE_FOR_AN_OF_MU_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) if(PO::m_SZ < N_OUTPUT_LIM){ for(uint i = PO::m_SZ;i < N_OUTPUT_LIM;i++){ PO::m_f.push_back(0); } PO::m_SZ = N_OUTPUT_LIM; } #define SET_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) VE AN(N_OUTPUT_LIM) #define SET_SUM_OF_MU_FOR_TR_POLYNOMIAL PO::m_f[i] = sum #define SET_SUM_OF_TR_MU_CO_FOR_TR_POLYNOMIAL AN[i] = sum #define SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(F,SZ,N_INPUT_START_NUM) uint N_INPUT_START_NUM; for(uint i = 0;i < SZ && searching;i++){ if(F[i] != zero){ N_INPUT_START_NUM = i; searching = false; } } #define SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(F,SZ,N_INPUT_MAX_NUM) uint N_INPUT_MAX_NUM; searching = true; for(uint i = (SZ) - 1;searching;i--){ if(F[i] != zero){ N_INPUT_MAX_NUM = i; searching = false; } } #define CONVOLUTION_FOR_MU_FOR_TR_POLYNOMIAL(J_MIN) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0; T sum{ zero }; for(uint j = J_MIN;j <= j_max;j++){ sum += PO::m_f[j] * f.PO::m_f[i - j]; } PO::m_f[i] = sum; #define CONVOLUTION_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL(J_MIN) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0; T& m_fi = AN[i]; for(uint j = J_MIN;j <= j_max;j++){ m_fi += PO::m_f[j] * f.PO::m_f[i - j]; } #define ZEROIFICATION_FOR_MU_FOR_TR_POLYNOMIAL for(uint i = 0;i < N_input_start_0_start_1;i++){ PO::m_f[i] = 0; } #define ZEROIFICATION_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL for(uint i = 0;i < N_input_start_0_start_1;i++){ AN[i] = 0; } #define CN(S1,S2) SUBSTITUTE_CN(S1,S2) #define SUBSTITUTE_CN(S1,S2) S1 ## S2 #define DF_0_OF__FOR_TR_POLYNOMIAL(MU,ACCESS_ENTRY) CN(CN(RE_ZERO_FOR_,MU),_FOR_TR_POLYNOMIAL_IF)(PO::m_SZ == 0); uint N_output_max = PO::m_SZ + f.PO::m_SZ - 2; if(N_output_max >= m_N){ N_output_max = m_N - 1; } CO uint N_output_lim = N_output_max + 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_POLYNOMIAL)(N_output_lim); for(uint i = N_output_max;searching;i--){ T sum{ zero }; for(uint j = 0;j <= i;j++){ sum += ACCESS_ENTRY * f.PO::OP[](i - j); } CN(CN(SET_SUM_OF_,MU),_FOR_TR_POLYNOMIAL); searching = i > 0; } #define DF_0_OF_MU_FOR_TR_POLYNOMIAL DF_0_OF__FOR_TR_POLYNOMIAL(MU,PO::m_f[j]) #define DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_0_OF__FOR_TR_POLYNOMIAL(TR_MU_CO,PO::OP[](j)) #define DF_1_OF__FOR_TR_POLYNOMIAL(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(PO::m_f,PO::m_SZ,N_input_start_0); CN(CN(RE_ZERO_FOR_,MU),_FOR_TR_POLYNOMIAL_IF)(searching); searching = true; SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(f,f.PO::m_SZ,N_input_start_1); #define DF_1_OF_MU_FOR_TR_POLYNOMIAL DF_1_OF__FOR_TR_POLYNOMIAL(MU) #define DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_1_OF__FOR_TR_POLYNOMIAL(TR_MU_CO) #define DF_2_OF_MU_FOR_TR_POLYNOMIAL SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(PO::m_f,PO::m_SZ,N_input_max_0); SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(f,f.PO::m_SZ < m_N ? f.PO::m_SZ:m_N,N_input_max_1); CO uint N_input_max_0_max_1 = N_input_max_0 + N_input_max_1; CO uint N_input_start_0_start_1 = N_input_start_0 + N_input_start_1; #define DF_2_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_2_OF_MU_FOR_TR_POLYNOMIAL #define DF_3_OF__FOR_TR_POLYNOMIAL(MU) CO uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1; CO uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1; CO uint N_output_max_fixed = N_output_lim_fixed - 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_POLYNOMIAL)(N_output_lim_fixed); for(uint i = N_output_max_fixed;i > N_input_start_0_max_1;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_POLYNOMIAL)(i - N_input_max_1); } searching = true; for(uint i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1:N_output_max_fixed;searching;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_POLYNOMIAL)(N_input_start_0); searching = i > N_input_start_0_start_1; } CN(CN(ZEROIFICATION_FOR_,MU),_FOR_TR_POLYNOMIAL); #define DF_3_OF_MU_FOR_TR_POLYNOMIAL DF_3_OF__FOR_TR_POLYNOMIAL(MU) #define DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_3_OF__FOR_TR_POLYNOMIAL(TR_MU_CO) #define DF_4_OF_MU_FOR_TR_POLYNOMIAL uint two_power = FFT_MU_border_1_2; uint exponent = FFT_MU_border_1_2_exponent; T two_power_inv{ FFT_MU_border_1_2_inv }; WH(N_input_truncated_deg_0_deg_1 >= two_power){ two_power *= 2; two_power_inv /= 2; exponent++; } VE f0{ FFT(PO::m_f,N_input_start_0,N_input_max_0 + 1,0,two_power,exponent) }; CO VE f1{ FFT(f.PO::m_f,N_input_start_1,N_input_max_1 + 1,0,two_power,exponent) }; for(uint i = 0;i < two_power;i++){ f0[i] *= f1[i]; } #define DF_4_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_4_OF_MU_FOR_TR_POLYNOMIAL #define DF_OF_INVERSE_FOR_TR_POLYNOMIAL(TYPE,RECURSION) CR_UINT N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_inv{ power_2,PO< TYPE >::CO_one() / f[0] }; WH(power_2 < N){ power = power_2; power_2 *= 2; f_inv.SetTruncation(power_2); RECURSION; } f_inv.SetTruncation(N); RE f_inv #define DF_OF_EXP_FOR_TR_POLYNOMIAL(TYPE,RECURSION) CR_UINT N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_exp{ power_2,PO< TYPE >::CO_one() }; WH(power_2 < N){ power = power_2; power_2 *= 2; f_exp.SetTruncation(power_2); RECURSION; } f_exp.SetTruncation(N); RE f_exp #define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_POLYNOMIAL(TYPE,BORDER_0,BORDER_1,BORDER_1_2,BORDER_1_2_EXPONENT,BORDER_1_2_INV) TE <> CE CO uint FFT_MU_border_0< TYPE > = BORDER_0; TE <> CE CO uint FFT_MU_border_1< TYPE > = BORDER_1; TE <> CE CO uint FFT_MU_border_1_2< TYPE > = BORDER_1_2; TE <> CE CO uint FFT_MU_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> CE CO uint FFT_MU_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TRPO< TYPE >& TRPO< TYPE >::OP*=(CO PO< TYPE >& f) { RE TRPO< TYPE >::FFT_MU(f); } TE <> TRPO< TYPE > Inverse(CO TRPO< TYPE >& f) { DF_OF_INVERSE_FOR_TR_POLYNOMIAL(TYPE,f_inv.TRMinus(f_inv.FFT_TRMU_CO(f,power,power_2).FFT_TRMU(f_inv,power,power_2),power,power_2)); } TE <> TRPO< TYPE > Exp(CO TRPO< TYPE >& f) { DF_OF_EXP_FOR_TR_POLYNOMIAL(TYPE,f_exp.TRMinus((TRIntegral(Differential(f_exp).FFT_TRMU_CO(Inverse(f_exp),power - 1,power_2),power).TRMinus(f,power,power_2)).FFT_TRMU(f_exp,power,power_2),power,power_2)); } #define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_POLYNOMIAL(TYPE) TE <> PO& PO::OP*=(CO PO& f) { if(m_SZ != 0){ VE v{}; v.swap(m_f); TRPO f_copy{ m_SZ + f.m_SZ - 1,MO(v) }; f_copy *= f; m_f = MO(f_copy.PO::m_f); m_SZ = m_f.SZ(); } RE *this; } IN CEXPR(ll,P,998244353);TE class TRPO;TE class PO{friend class TRPO;PR:VE m_f;uint m_SZ;PU:IN PO();IN PO(CO T& t);IN PO(CO PO& f);IN PO(PO&& f);IN PO(C_UINT i,CO T& t);IN PO(VE&& f);PO& OP=(CO T& t);PO& OP=(CO PO& f);PO& OP=(PO&& f);IN CO T& OP[](C_UINT i) CO;IN T& OP[](C_UINT i);IN T OP()(CO T& t) CO;IN PO& OP+=(CO T& t);PO& OP+=(CO PO& f);IN PO& OP-=(CO T& t);PO& OP-=(CO PO& f);PO& OP*=(CO T& t);PO& OP*=(CO PO& f);PO& OP/=(CO T& t);PO& OP/=(CO PO& f);PO& OP%=(CO T& t);PO& OP%=(CO PO& f);IN PO OP-() CO;PO& OP<<=(CO T& t);IN CO VE& GetCoefficient() CO NE;IN CR_UINT SZ() CO NE;IN void swap(PO& f);IN void swap(VE& f);void ReMORedundantZero();IN string Display() CO NE;ST IN CO PO& zero();ST IN CO T& CO_zero();ST IN CO T& CO_one();ST IN CO T& CO_minus_one();ST IN CO T& factorial(C_UINT i);ST IN CO T& factorial_inverse(C_UINT i);};TE bool OP==(CO PO& f0,CO T& t1);TE bool OP==(CO PO& f0,CO PO& f1);TE IN bool OP!=(CO PO& f0,CO P& f1);TE IN PO OP+(CO PO& f0,CO P& f1);TE IN PO OP-(CO PO& f);TE IN PO OP-(CO PO& f0,CO P& f1);TE IN PO OP*(CO PO& f0,CO P& f1);TE IN PO OP/(CO PO& f0,CO P& f1);TE IN PO OP%(CO PO& f0,CO P& f1);TE IN PO OP<<(CO PO& f,CO T& t);TE IN T& Prod(LI& f);TE class TRPO;TE TRPO TRDifferential(CO TRPO& f,C_UINT N_output_start_plus_one);TE TRPO TRIntegral(CO TRPO& f,C_UINT N_output_start);TE class TRPO;TE TRPO TRDifferential(CO TRPO& f,C_UINT N_output_start_plus_one);TE TRPO TRIntegral(CO TRPO& f,C_UINT N_output_start);TE class TRPO :PU PO{friend TRPO TRDifferential(CO TRPO& f,C_UINT N_output_start_plus_one);friend TRPO TRIntegral(CO TRPO& f,C_UINT N_output_start);PR:uint m_N;PU:IN TRPO(C_UINT N = 0);IN TRPO(CO TRPO& f);IN TRPO(TRPO&& f);IN TRPO(C_UINT N,CO T& t);TRPO(C_UINT N,CO PO& f);IN TRPO(C_UINT N,PO&& f);IN TRPO(C_UINT N,C_UINT i,CO T& t);IN TRPO(C_UINT N,VE&& f);IN TRPO& OP=(CO TRPO& f);IN TRPO& OP=(TRPO&& f);IN TRPO& OP=(CO T& t);IN TRPO& OP=(CO PO& f);IN TRPO& OP=(PO&& f);IN TRPO& OP+=(CO T& t);IN TRPO& OP+=(CO PO& f);IN TRPO& OP+=(CO TRPO& f);TRPO& TRPlus(CO PO& f,C_UINT N_input_start,C_UINT N_input_limit);IN TRPO& OP-=(CO T& t);IN TRPO& OP-=(CO PO& f);IN TRPO& OP-=(CO TRPO& f);TRPO& TRMinus(CO PO& f,C_UINT N_input_start,C_UINT N_input_limit);IN TRPO& OP*=(CO T& t);TRPO& OP*=(CO PO& f);TRPO& FFT_MU(CO PO& f);TRPO& TRMU(CO PO& f,C_UINT N_input_start,C_UINT N_input_lim);TRPO& FFT_TRMU(CO PO& f,C_UINT N_input_start,C_UINT N_input_lim);TRPO TRMU_CO(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim) CO;TRPO FFT_TRMU_CO(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim) CO;IN TRPO& OP/=(CO T& t);IN TRPO& OP/=(CO TRPO& t);IN TRPO& OP%=(CO T& t);IN TRPO OP-() CO;IN void SetTruncation(C_UINT N) NE;IN CR_UINT GetTruncation() CO NE;IN TRPO& TruncateInitial(C_UINT N) NE;IN TRPO& TruncateFinal(C_UINT N) NE;};TE IN CE CO uint FFT_MU_border_0{};TE IN CE CO uint FFT_MU_border_1{};TE IN CE CO uint FFT_MU_border_1_2{};TE IN CE CO uint FFT_MU_border_1_2_exponent{};TE IN CE CO uint FFT_MU_border_1_2_inv{};TE IN TRPO OP+(CO TRPO& f0,CO P& f1);TE IN TRPO OP-(CO TRPO& f);TE IN TRPO OP-(CO TRPO& f0,CO P& f1);TE IN TRPO OP*(CO TRPO& f0,CO P& f1);TE IN TRPO OP/(CO TRPO& f0,CO P& f1);TE IN TRPO OP%(CO TRPO& f0,CO T& t1);TE IN TRPO Differential(CO TRPO& f);TE IN TRPO Differential(C_UINT i,CO TRPO& f);TE TRPO TRDifferential(CO TRPO& f,C_UINT N_output_start_plus_one);TE IN TRPO Integral(CO TRPO& f);TE TRPO TRIntegral(CO TRPO& f,C_UINT N_output_start);TE TRPO Inverse(CO TRPO& f);TE TRPO Exp(CO TRPO& f);TE IN TRPO Log(CO TRPO& f);TE TRPO Power(CO TRPO& f,CO T& t);TE IN CE CO uint LimitOfPowerForFFT{};TE IN CE CO uint BorderForFFT{};TE IN CO T (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT];TE IN CO T (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT];TE IN VE FFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent);TE IN VE FFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent);TE VE IFFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent);TE VE IFFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent);TE <> IN CE CO uint LimitOfPowerForFFT > = 24;TE <> IN CE CO uint BorderForFFT > = 4; TE <> IN CO Mod<998244353> (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT > ] ={Mod<998244353>(1) ,Mod<998244353>(998244352) ,Mod<998244353>(911660635) ,Mod<998244353>(625715529) ,Mod<998244353>(373294451) ,Mod<998244353>(827987769) ,Mod<998244353>(280333251) ,Mod<998244353>(581015842) ,Mod<998244353>(628092333) ,Mod<998244353>(300892551) ,Mod<998244353>(586046298) ,Mod<998244353>(615001099) ,Mod<998244353>(318017948) ,Mod<998244353>(64341522) ,Mod<998244353>(106061068) ,Mod<998244353>(304605202) ,Mod<998244353>(631920086) ,Mod<998244353>(857779016) ,Mod<998244353>(841431251) ,Mod<998244353>(805775211) ,Mod<998244353>(390359979) ,Mod<998244353>(923521) ,Mod<998244353>(961) ,Mod<998244353>(31)};RE PRT;}TE <> IN CO Mod<998244353> (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT > ] ={Mod<998244353>(1) ,Mod<998244353>(998244352) ,Mod<998244353>(86583718) ,Mod<998244353>(488723995) ,Mod<998244353>(369330050) ,Mod<998244353>(543653592) ,Mod<998244353>(382946991) ,Mod<998244353>(844956623) ,Mod<998244353>(91420391) ,Mod<998244353>(433414612) ,Mod<998244353>(288894979) ,Mod<998244353>(260490556) ,Mod<998244353>(857007890) ,Mod<998244353>(736054570) ,Mod<998244353>(474649464) ,Mod<998244353>(948509906) ,Mod<998244353>(114942468) ,Mod<998244353>(962405921) ,Mod<998244353>(667573957) ,Mod<998244353>(46809892) ,Mod<998244353>(304321983) ,Mod<998244353>(30429817) ,Mod<998244353>(293967900) ,Mod<998244353>(128805723)};RE PRT;}TE ST VE FFT_Body(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent,CO T (&PRT)[LimitOfPowerForFFT]);TE ST VE FFT_Body(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent,C_UINT start,C_UINT depth,CO T (&PRT)[LimitOfPowerForFFT]);TE IN VE FFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent) { RE FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power,exponent,0,1,PrimitiveRootOfTwoForFFT()); }TE IN VE FFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent) { RE FFT_Body(f,N_input_start,N_input_lim,N_input_shift,N_output_start,N_output_lim,N_output_shift,two_power,exponent,PrimitiveRootOfTwoForFFT()); }TE VE IFFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent){VE AN{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT()) };CO uint SZ = AN.SZ();for(uint i = 0;i < SZ;i++){AN[i] *= two_power_inv;}RE AN;}TE VE IFFT(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,CO T& two_power_inv,C_UINT exponent){VE AN{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,N_output_start,N_output_lim,N_output_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT()) };uint SZ = AN.SZ();CO uint N_output_length = N_output_lim - N_output_start + N_output_shift;if(SZ < N_output_length){SZ = N_output_length;}for(uint i = N_output_shift;i < SZ;i++){AN[i] *= two_power_inv;}RE AN;}TE ST VE FFT_Body(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT N_output_start,C_UINT N_output_lim,C_UINT N_output_shift,C_UINT two_power,C_UINT exponent,CO T (&PRT)[LimitOfPowerForFFT]){CO uint length = N_output_lim - N_output_start + N_output_shift;VE AN(length);if(two_power == 1){if(N_input_shift == 0 && N_output_shift < length){if(N_input_start < N_input_lim){AN[N_output_shift] = f[N_input_start];}}} else {CO T& zeta = PRT[exponent];T zeta_power = PRT[0];uint N_output_start_copy = N_output_start;uint digit = 0;if(N_output_start_copy != 0){if(N_output_start_copy % 2 == 1){zeta_power *= zeta;}N_output_start_copy /= 2;digit++;}WH(N_output_start_copy != 0){if(N_output_start_copy % 2 == 1){zeta_power *= PRT[exponent - digit];}N_output_start_copy /= 2;digit++;}CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;VE AN_sub0{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,0,2,PRT) };VE AN_sub1{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,1,2,PRT) };for(uint i = N_output_start;i < N_output_lim;i++){CO uint i_sub = i % two_power_sub;AN[i - N_output_start + N_output_shift] = AN_sub0[i_sub] + zeta_power * AN_sub1[i_sub];zeta_power *= zeta;}}RE AN;}TE ST VE FFT_Body(CO VE& f,C_UINT N_input_start,C_UINT N_input_lim,C_UINT N_input_shift,C_UINT two_power,C_UINT exponent,C_UINT start,C_UINT depth,CO T (&PRT)[LimitOfPowerForFFT]){VE AN(two_power);CO uint start_depth = start + ((two_power - 1) * depth);CO uint N_input_length = N_input_lim - N_input_start + N_input_shift;if(start < N_input_length && N_input_shift <= start_depth){uint j_min;if(start < N_input_shift){CO uint N_input_shift_shift = N_input_shift - start;j_min = N_input_shift_shift / depth + (N_input_shift_shift % depth == 0 ? 0:1);} else {j_min = 0;}uint j_lim;if(N_input_length <= start_depth){CO uint N_input_length_shift = N_input_length - start;j_lim = N_input_length_shift / depth + (N_input_length_shift % depth == 0 ? 0:1);} else {j_lim = two_power;}CO T zero{ 0 };uint count = 0;uint index_hit;uint j_hit;for(uint j = j_min;j < j_lim && count < 2;j++){CO uint index = start + j * depth - N_input_shift + N_input_start;if(f[index] != zero){if(count == 0){index_hit = index;j_hit = j;}count++;}}if(count == 1){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };T zeta_power_2{ zeta };WH(j_hit != 0){if(j_hit % 2 == 1){zeta_power *= zeta_power_2;}zeta_power_2 *= zeta_power_2;j_hit /= 2;}AN[0] = f[index_hit];for(uint i = 1;i < two_power;i++){AN[i] = zeta_power * AN[i-1];}} else if(count > 1){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };CE C_UINT border = BorderForFFT;if(exponent < border){for(uint i = 0;i < two_power;i++){T& AN_i = AN[i];T zeta_power_power{ one };T zeta_power_power_2{ zeta_power };uint j_min_copy = j_min;WH(j_min_copy != 0){if(j_min_copy % 2 == 1){zeta_power_power *= zeta_power_power_2;}zeta_power_power_2 *= zeta_power_power_2;j_min_copy /= 2;}uint index = start + j_min * depth - N_input_shift + N_input_start;for(uint j = j_min;j < j_lim;j++){AN_i += zeta_power_power * f[index];zeta_power_power *= zeta_power;index += depth;}zeta_power *= zeta;}} else {CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;CO uint depth_sub = depth * 2;VE AN_sub0{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,start,depth_sub,PRT) };VE AN_sub1{ FFT_Body(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,start + depth,depth_sub,PRT) };for(uint i = 0;i < two_power;i++){CO uint i_sub = i % two_power_sub;AN[i] = AN_sub0[i_sub] + zeta_power * AN_sub1[i_sub];zeta_power *= zeta;}}}}RE AN;}TE IN TRPO::TRPO(C_UINT N):PO(),m_N(N) {}TE IN TRPO::TRPO(CO TRPO& f):PO(f),m_N(f.m_N) {}TE IN TRPO::TRPO(TRPO&& f):PO(MO(f)),m_N(MO(f.m_N)) {}TE IN TRPO::TRPO(C_UINT N,CO T& t):PO(t),m_N(N) {}TE TRPO::TRPO(C_UINT N,CO PO& f):PO(),m_N(N){CR_UINT SZ = f.PO::m_SZ < m_N ? f.PO::m_SZ:m_N;for(uint i = 0;i < SZ;i++){PO::m_f.push_back(f.PO::m_f[i]);PO::m_SZ++;}}TE IN TRPO::TRPO(C_UINT N,PO&& f):PO(MO(f)),m_N(N) {};TE IN TRPO::TRPO(C_UINT N,C_UINT i,CO T& t):PO(),m_N(N) { if(i < m_N ? t != PO::CO_zero():false){ PO::OP[](i) = t; } }TE IN TRPO::TRPO(C_UINT N,VE&& f):PO(MO(f)),m_N(N){WH(PO::m_SZ > m_N){PO::m_f.pop_back();PO::m_SZ--;}}TE IN TRPO& TRPO::OP=(CO TRPO& f) { PO::OP=(f); m_N = f.m_N; RE *this; }TE IN TRPO& TRPO::OP=(TRPO&& f) { PO::OP=(MO(f)); m_N = MO(f.m_N); RE *this; }TE IN TRPO& TRPO::OP=(CO T& t) { PO::OP=(t); RE *this; }TE IN TRPO& TRPO::OP=(CO PO& f) { RE OP=(TRPO(m_N,f)); }TE IN TRPO& TRPO::OP=(PO&& f) { RE OP=(TRPO(m_N,MO(f))); }TE IN TRPO& TRPO::OP+=(CO T& t) { PO::OP+=(t); RE *this; }TE IN TRPO& TRPO::OP+=(CO PO& f) { RE TRPO::TRPlus(f,0,f.PO::m_SZ); }TE IN TRPO& TRPO::OP+=(CO TRPO& f) { RE m_N == 0 ? OP=(f):TRPO::TRPlus(f,0,f.PO::m_SZ); }TE TRPO& TRPO::TRPlus(CO PO& f,C_UINT N_output_start,C_UINT N_output_limit){CR_UINT SZ = N_output_limit < m_N ? N_output_limit < f.PO::m_SZ ? N_output_limit:f.PO::m_SZ:m_N < f.PO::m_SZ ? m_N:f.PO::m_SZ;CR_UINT SZ_min = PO::m_SZ < SZ ? PO::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO::m_f[i] += f.PO::m_f[i];}for(uint i = PO::m_SZ;i < SZ;i++){PO::m_f.push_back(f.PO::m_f[i]);PO::m_SZ++;}RE *this;}TE IN TRPO& TRPO::OP-=(CO T& t) { PO::OP-=(t); RE *this; }TE IN TRPO& TRPO::OP-=(CO PO& f) { RE TRPO::TRMinus(f,0,f.PO::m_SZ); }TE IN TRPO& TRPO::OP-=(CO TRPO& f) { RE m_N == 0 ? OP=(-f):TRPO::TRMinus(f,0,f.PO::m_SZ); }TE TRPO& TRPO::TRMinus(CO PO& f,C_UINT N_output_start,C_UINT N_output_limit){CR_UINT SZ = N_output_limit < m_N ? N_output_limit < f.PO::m_SZ ? N_output_limit:f.PO::m_SZ:m_N < f.PO::m_SZ ? m_N:f.PO::m_SZ;CR_UINT SZ_min = PO::m_SZ < SZ ? PO::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO::m_f[i] -= f.PO::m_f[i];}for(uint i = PO::m_SZ;i < SZ;i++){PO::m_f.push_back(- f.PO::m_f[i]);PO::m_SZ++;}RE *this;}TE IN TRPO& TRPO::OP*=(CO T& t) { PO::OP*=(t); RE *this; }DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_POLYNOMIAL(Mod<998244353>,12,512,1024,10,997269505); TE TRPO& TRPO::OP*=(CO PO& f){CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO::m_SZ == 0);DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(searching);DF_2_OF_MU_FOR_TR_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= m_N);DF_3_OF_MU_FOR_TR_POLYNOMIAL;}RE *this;}TE TRPO& TRPO::FFT_MU(CO PO& f){CE C_UINT border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO::m_SZ == 0);DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(searching);DF_2_OF_MU_FOR_TR_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE C_UINT border_1 = FFT_MU_border_1;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_4_OF_MU_FOR_TR_POLYNOMIAL;PO::m_f = IFFT(f0,0,two_power,0,0,N_output_lim_fixed - N_input_start_0_start_1,N_input_start_0_start_1,two_power,two_power_inv,exponent);PO::m_SZ = PO::m_f.SZ();}}RE *this;}TE TRPO& TRPO::TRMU(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim){CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;DF_2_OF_MU_FOR_TR_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;}RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);DF_3_OF_MU_FOR_TR_POLYNOMIAL;}RE *this;}TE TRPO& TRPO::FFT_TRMU(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim){CE C_UINT border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){DF_0_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_1_OF_MU_FOR_TR_POLYNOMIAL;DF_2_OF_MU_FOR_TR_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;}RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE C_UINT border_1 = FFT_MU_border_1;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_POLYNOMIAL;} else {DF_4_OF_MU_FOR_TR_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if(N_output_start < N_input_start_0_start_1){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;f0 = IFFT(f0,0,two_power,0,N_output_start_shifted,N_output_lim_shifted,N_output_shift_shifted,two_power,two_power_inv,exponent);SET_VE_FOR_AN_OF_MU_FOR_TR_POLYNOMIAL(N_output_lim_fixed);for(uint i = N_output_start;i < N_output_lim_fixed;i++){PO::m_f[i] = f0[i];}}}RE *this;}TE TRPO TRPO::TRMU_CO(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim) CO{CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO(m_N,MO(AN));}DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;DF_2_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;}RE_ZERO_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO(m_N,MO(AN));}TE TRPO TRPO::FFT_TRMU_CO(CO PO& f,C_UINT N_output_start,C_UINT N_output_lim) CO{CE C_UINT border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO(m_N,MO(AN));}DF_1_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;DF_2_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N;if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;}RE_ZERO_FOR_TR_MU_CO_FOR_TR_POLYNOMIAL_IF(N_input_start_0_start_1 >= N_output_lim_fixed);CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE C_UINT border_1 = FFT_MU_border_1;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO(m_N,MO(AN));}DF_4_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if(N_output_start < N_input_start_0_start_1){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;RE TRPO(m_N,IFFT(f0,0,two_power,0,N_output_start_shifted,N_output_lim_shifted,N_output_shift_shifted,two_power,two_power_inv,exponent));}TE IN TRPO& TRPO::OP/=(CO T& t) { PO::OP/=(t); RE *this; }TE IN TRPO& TRPO::OP/=(CO TRPO& f) { RE OP*=(Inverse(m_N > f.m_N ? f:TRPO(m_N,f))); }TE IN TRPO& TRPO::OP%=(CO T& t) { PO::OP%=(t); RE *this; }TE IN TRPO TRPO::OP-() CO { RE TRPO(m_N).OP-=(*this); }TE IN void TRPO::SetTruncation(C_UINT N) NE { m_N = N; TruncateFinal(m_N); }TE IN CR_UINT TRPO::GetTruncation() CO NE { RE m_N; }TE IN TRPO& TRPO::TruncateInitial(C_UINT N) NE { CR_UINT SZ = N < PO::m_SZ ? N:PO::m_SZ; for(uint i = 0;i < SZ;i++){ PO::m_f[i] = 0; } RE *this; }TE IN TRPO& TRPO::TruncateFinal(C_UINT N) NE { WH(PO::m_SZ > N){ PO::m_f.pop_back(); PO::m_SZ--; } RE *this; }TE IN TRPO OP+(CO TRPO& f0,CO P& f1) { RE TRPO(f0).OP+=(f1); }TE IN TRPO OP-(CO TRPO& f) { RE TRPO(f).OP*=(PO::CO_minus_one()); }TE IN TRPO OP-(CO TRPO& f0,CO P& f1) { RE TRPO(f0).OP-=(f1); }TE IN TRPO OP*(CO TRPO& f0,CO P& f1) { RE TRPO(f0).OP*=(f1); }TE IN TRPO OP/(CO TRPO& f0,CO P& f1) { RE TRPO(f0).OP*=(Inverse(f1)); }TE IN TRPO OP%(CO TRPO& f0,CO T& t1) { RE TRPO(f0).OP%=(t1); }TE IN TRPO Differential(CO TRPO& f) { RE TRDifferential(f,1); }TE IN TRPO Differential(C_UINT i,CO TRPO& f) { RE i == 0 ? f:Differential(i - 1,Differential(f)); }TE TRPO TRDifferential(CO TRPO& f,C_UINT N_output_start_plus_one){if(f.m_N == 0){RE TRPO();}TRPO f_dif{ f.m_N - 1 };if(N_output_start_plus_one < f.PO::m_SZ){for(uint i = 1;i < N_output_start_plus_one;i++){f_dif.PO::m_f.push_back(0);}for(uint i = N_output_start_plus_one;i < f.PO::m_SZ;i++){f_dif.PO::m_f.push_back(i * f.PO::m_f[i]);}f_dif.PO::m_SZ = f.PO::m_SZ - 1;}RE f_dif;}TE IN TRPO Integral(CO TRPO& f) { RE TRIntegral(f,1); }TE TRPO TRIntegral(CO TRPO& f,C_UINT N_output_start){TRPO f_int{ f.m_N + 1 };if(N_output_start <= f.PO::m_SZ){for(uint i = 0;i < N_output_start;i++){f_int.PO::m_f.push_back(0);}for(uint i = N_output_start;i <= f.PO::m_SZ;i++){f_int.PO::m_f.push_back(f.PO::m_f[i - 1] / T(i));}f_int.PO::m_SZ = f.PO::m_SZ + 1;}RE f_int;}TE TRPO Inverse(CO TRPO& f){DF_OF_INVERSE_FOR_TR_POLYNOMIAL(T,f_inv.TRMinus(f_inv.TRMU_CO(f,power,power_2).TRMU(f_inv,power,power_2),power,power_2));}TE TRPO Exp(CO TRPO& f){DF_OF_EXP_FOR_TR_POLYNOMIAL(T,f_exp.TRMinus((TRIntegral(Differential(f_exp).TRMU_CO(Inverse(f_exp),power - 1,power_2),power).TRMinus(f,power,power_2)).TRMU(f_exp,power),power,power_2));}TE IN TRPO Log(CO TRPO& f) { RE Integral(Differential(f) /= f); }TE IN TRPO Power(CO TRPO& f,CO T& t) { RE Exp(Log(f) *= t); }TE IN PO::PO():m_f(),m_SZ(0) {}TE IN PO::PO(CO T& t):PO() { if(t != CO_zero()){ OP[](0) = t; } }TE IN PO::PO(CO PO& f):m_f(f.m_f),m_SZ(f.m_SZ) {}TE IN PO::PO(PO&& f):m_f(MO(f.m_f)),m_SZ(MO(f.m_SZ)) {}TE IN PO::PO(C_UINT i,CO T& t):PO() { if(t != CO_zero()){ OP[](i) = t; } }TE IN PO::PO(VE&& f):m_f(MO(f)),m_SZ(m_f.SZ()) {}TE IN PO& PO::OP=(CO T& t) { m_f.clear(); m_SZ = 0; OP[](0) = t; RE *this; }TE IN PO& PO::OP=(CO PO& f) { m_f = f.m_f; m_SZ = f.m_SZ; RE *this; }TE IN PO& PO::OP=(PO&& f) { m_f = move(f.m_f); m_SZ = move(f.m_SZ); RE *this; }TE CO T& PO::OP[](C_UINT i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE IN T& PO::OP[](C_UINT i){if(m_SZ <= i){CO T& z = CO_zero();WH(m_SZ <= i){m_f.push_back(z);m_SZ++;}}RE m_f[i];}TE IN T PO::OP()(CO T& t) CO { RE (*this % (PO(1,CO_one()) - t))[0]; }TE IN PO& PO::OP+=(CO T& t) { OP[](0) += t; RE *this; }TE PO& PO::OP+=(CO PO& f){for(uint i = 0;i < f.m_SZ;i++){OP[](i) += f.m_f[i];}RE *this;}TE IN PO& PO::OP-=(CO T& t) { OP[](0) -= t; RE *this; }TE PO& PO::OP-=(CO PO& f){for(uint i = 0;i < f.m_SZ;i++){OP[](i) -= f.m_f[i];}RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_POLYNOMIAL(Mod<998244353>);TE PO& PO::OP*=(CO T& t){if(m_SZ == 0 || t == CO_one()){RE *this;}if(t == CO_zero()){RE OP=(zero());}for(uint i = 0;i < m_SZ;i++){OP[](i) *= t;}RE *this;}TE PO& PO::OP*=(CO PO& f){if(m_SZ == 0){RE *this;}if(f.m_SZ == 0){RE OP=(zero());}CO uint SZ = m_SZ + f.m_SZ - 1;PO product{}; for(uint i = 0;i < SZ;i++){T& product_i = product[i];CO uint j_min = m_SZ <= i ? i - m_SZ + 1:0;CO uint j_lim = i < f.m_SZ ? i + 1:f.m_SZ;for(uint j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(MO(product));}TE PO& PO::OP/=(CO T& t){if(t == CO_one()){RE *this;}for(uint i = 0;i < m_SZ;i++){OP[](i) /= t;}RE *this;}TE PO& PO::OP/=(CO PO& f){if(m_SZ >= f.m_SZ){assert(f.m_SZ > 0);uint SZ0 = m_SZ - f.m_SZ + 1;TRPO f0_copy(SZ0);for(uint d0 = 0;d0 < SZ0;d0++){f0_copy.PO::m_f.push_back(m_f[m_SZ - 1 - d0]);}f0_copy.PO::m_SZ = SZ0;TRPO f1_copy(SZ0);uint SZ1 = SZ0 < f.m_SZ ? SZ0:f.m_SZ;for(uint d1 = 0;d1 < SZ1;d1++){f1_copy.PO::m_f.push_back(f.m_f[f.m_SZ - 1 - d1]);}f1_copy.PO::m_SZ = SZ1;f0_copy /= f1_copy;for(uint d0 = 0;d0 < SZ0;d0++){m_f[d0] = f0_copy[ SZ0 - 1 - d0 ];}WH(m_SZ > SZ0){m_f.pop_back();m_SZ--;}} else {PO::m_f.clear();PO::m_SZ = 0;}RE *this;}TE PO& PO::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(uint i = 0;i < m_SZ;i++){OP[](i) %= t;}RE *this;}TE PO& PO::OP%=(CO PO& f){if(m_SZ >= f.m_SZ){OP-=((*this / f) * f);ReMORedundantZero();}RE *this;}TE IN PO PO::OP-() CO { RE PO().OP-=(*this); }TE PO& PO::OP<<=(CO T& t){if(m_SZ > 0){ST T factorial_curr = 1;ST VE factorial = { 1,1 };ST T factorial_inv_curr = 1;ST VE factorial_inv = { 1,1 };uint SZ = factorial.SZ();WH(SZ < m_SZ){factorial.push_back(factorial_curr *= SZ);factorial_inv.push_back(factorial_inv_curr /= SZ);SZ++;}for(uint d = 0;d < m_SZ;d++){m_f[d] *= factorial[d];}TRPO f{ m_SZ * 2 };T power_t = CO_one();for(uint d = 0;d < m_SZ;d++){f[m_SZ - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for(uint d = 0;d < m_SZ;d++){m_f[d] = f.PO::m_f[d + m_SZ - 1] * factorial_inv[d];}}RE *this;}TE IN CO VE& PO::GetCoefficient() CO NE { RE m_f; }TE IN CR_UINT PO::SZ() CO NE { RE m_SZ; }TE IN void PO::swap(PO& f) { m_f.swap(f.m_f); swap(m_SZ,f.m_SZ); }TE IN void PO::swap(VE& f) { m_f.swap(f); m_SZ = m_f.SZ(); }TE void PO::ReMORedundantZero(){CO T& z = CO_zero();WH(m_SZ > 0 ? m_f[m_SZ - 1] == z:false){m_f.pop_back();m_SZ--;}RE;}TE string PO::Display() CO NE{string s = "(";if(m_SZ > 0){s += to_string(m_f[0]);for(uint i = 1;i < m_SZ;i++){s += ", " + to_string(m_f[i]);}}s += ")";RE s;}TE IN CO PO& PO::zero() { ST CO PO z{}; RE z; }TE IN CO T& PO::CO_zero() { ST CO T z{ 0 }; RE z; }TE IN CO T& PO::CO_one() { ST CO T o{ 1 }; RE o; }TE IN CO T& PO::CO_minus_one() { ST CO T m{ -1 }; RE m; }TE IN CO T& PO::factorial(C_UINT i) { ST VE memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint SZ = 2; WH(SZ <= i){ memory.push_back(curr *= SZ++); } RE memory[i]; }TE IN CO T& PO::factorial_inverse(C_UINT i) { ST VE memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint SZ = 2; WH(SZ <= i){ memory.push_back(curr /= SZ++); } RE memory[i]; }TE bool OP==(CO PO& f0,CO T& t1){C_UINT SZ = f0.SZ();CO T& zero = PO::CO_zero();for(uint i = 1;i < SZ;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE bool OP==(CO PO& f0,CO PO& f1){CR_UINT SZ0 = f0.SZ();CR_UINT SZ1 = f1.SZ();CR_UINT SZ = SZ0 < SZ1 ? SZ1:SZ0;for(uint i = 0;i < SZ;i++){if(f0[i] != f1[i]){RE false;}}RE true;}TE IN bool operator!=(CO PO& f0,CO P& f1) { RE !(f0 == f1); }TE IN PO operator+(CO PO& f0,CO P& f1) { PO f = f0; f += f1; RE f; }TE IN PO operator-(CO PO& f) { RE PO::zero() - f; }TE IN PO operator-(CO PO& f0,CO P& f1) { PO f = f0; RE f.operator-=(f1); }TE IN PO operator*(CO PO& f0,CO P& f1) { PO f = f0; RE f.operator*=(f1); }TE IN PO operator/(CO PO& f0,CO P& f1) { PO f = f0; RE f.operator/=(f1); }TE IN PO operator%(CO PO& f0,CO P& f1) { PO f = f0; RE f.operator%=(f1); }TE PO operator<<(CO PO& f,CO T& t) { RE PO(f) <<= t; };TE IN T& Prod(LI& f){if(f.empty()){f.push_back(T(1));}if(f.SZ() == 1){RE f.front();}auto I = f.begin(),end = f.end();WH(I != end){T& t = *I;I++;if(I != end){t = t * *I;I = f.erase(I);}}RE Prod(f);} TE using TT = VE >;TE class MA{PR:TT m_M;PU:IN MA(CO T& t = T()) NE;IN MA(C_INT t) NE;TE IN MA(CO T& t0,CO T& t1,CO Args&... args) NE;TE IN MA(T&& t0,T&& t1,Args&&... args) NE;IN MA(CO MA& mat) NE;IN MA(MA&& mat) NE;TE IN MA(CO TT& M) NE;TE IN MA(TT&& M) NE;IN MA& operator=(CO MA& mat) NE;IN MA& operator=(MA&& mat) NE;MA& operator+=(CO MA& mat);MA& operator-=(CO MA& mat);MA& operator*=(CO T& scalar) NE;IN MA& operator*=(CO MA& mat) NE;MA& operator%=(CO T& scalar) NE;IN TT& RefTable() NE;IN CO TT& GetTable() CO NE;ST IN CO MA& Zero() NE;ST IN CO MA& Unit() NE;ST MA Scalar(CO T& t) NE;PR:ST IN void COructTable(TT& M,VE& vec) NE;TE ST void COructTable(TT& M,VE& vec,CO T& t,CO Args&... args) NE;TE ST void COructTable(TT& M,VE& vec,T&& t,Args&&... args) NE;ST MA Zero_Body() NE;};TE IN MA operator==(CO MA& mat1,CO MA& mat2) NE;TE IN MA operator!=(CO MA& mat1,CO MA& mat2) NE;TE IN MA operator+(CO MA& mat1,CO MA& mat2);TE IN MA operator-(CO MA& mat1,CO MA& mat2);TE MA operator*(CO MA& mat1,CO MA& mat2);TE IN MA operator*(CO MA& mat,CO T& scalar);TE IN MA operator*(CO T& scalar,CO MA& mat);TE IN MA operator%(CO MA& mat,CO T& scalar);TE MA Transpose(CO MA& mat);TE T Trace(CO MA& mat);TE IN MA::MA(CO T& t) NE:m_M() { operator=(Scalar(t)); }TE IN MA::MA(C_INT t) NE:MA(T(t)) {}TE TE MA::MA(CO T& t0,CO T& t1,CO Args&... args) NE: m_M(){VE vec{};COructTable(m_M,vec,t0,t1,args...);}TE TE MA::MA(T&& t0,T&& t1,Args&&... args) NE: m_M(){VE vec{};COructTable(m_M,vec,MO(t0),MO(t1),MO(args)...);}TE IN MA::MA(CO MA& mat) NE:m_M(mat.m_M) {}TE IN MA::MA(MA&& mat) NE:m_M(MO(mat.m_M)) {}TE TE IN MA::MA(CO TT& M) NE:m_M(M) {}TE TE IN MA::MA(TT&& M) NE:m_M(MO(M)) {}TE IN MA& MA::operator=(CO MA& mat) NE { m_M = mat.m_M; RE *this; }TE IN MA& MA::operator=(MA&& mat) NE { m_M = move(mat.m_M); RE *this; }TE MA& MA::operator+=(CO MA& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin(); WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); WH(I1xy != end1xy){*I1xy += *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE MA& MA::operator-=(CO MA& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin(); WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); WH(I1xy != end1xy){*I1xy -= *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE MA& MA::operator*=(CO T& scalar) NE{for(auto Iy = m_M.begin(),endy = m_M.end();Iy != endy;Iy++){for(auto Ixy = Iy->begin(),endxy = Iy->end();Ixy != endxy;Ixy++){*Ixy *= scalar;}}RE *this;}TE IN MA& MA::operator*=(CO MA& mat) NE { RE operator=(MO(*this * mat)); }TE MA& MA::operator%=(CO T& scalar) NE{for(auto Iy = m_M.begin(),endy = m_M.end();Iy != endy;Iy++){for(auto Ixy = Iy->begin(),endxy = Iy->end();Ixy != endxy;Ixy++){*Ixy %= scalar;}}RE *this;}TE IN TT& MA::RefTable() NE { RE m_M; }TE IN CO TT& MA::GetTable() CO NE { RE m_M; }TE IN CO MA& MA::Zero() NE { ST CO MA zero = MO(Zero_Body()); RE zero; }TE IN CO MA& MA::Unit() NE { ST CO MA unit = MO(Scalar(T(1))); RE unit; }TE MA MA::Zero_Body() NE{VE vec(X);TT M(Y,vec);RE MA(MO(M));}TE MA MA::Scalar(CO T& t) NE{MA M{ MO(Zero_Body()) };CE CO uint minXY = Y < X ? Y:X;for(uint y = 0;y < minXY;y++){M.m_M[y][y] = t;}RE M;}TE IN void MA::COructTable(TT& M,VE& vec) NE { M.push_back(MO(vec)); }TE TE void MA::COructTable(TT& M,VE& vec,CO T& t,CO Args&... args) NE{vec.push_back(t);if(vec.SZ() == X){VE v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,args...);}RE;}TE TE void MA::COructTable(TT& M,VE& vec,T&& t,Args&&... args) NE{vec.push_back(MO(t));if(vec.SZ() == X){VE v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,MO(args)...);}RE;}TE IN MA operator==(CO MA& mat1,CO MA& mat2) NE { RE mat1.GetTable() == mat2.GetTable(); }TE IN MA operator!=(CO MA& mat1,CO MA& mat2) NE { RE !(mat1 == mat2); }TE IN MA operator+(CO MA& mat1,CO MA& mat2) { RE MA(mat1) += mat2; }TE IN MA operator-(CO MA& mat1,CO MA& mat2) { RE MA(mat1) -= mat2; }TE IN MA operator*(CO MA& mat1,CO MA& mat2){CO TT& M1 = mat1.GetTable();CO TT& M2 = mat2.GetTable();TT M_prod{};auto begin2x = M2.begin();for(auto I1y = M1.begin(),end1y = M1.end();I1y != end1y;I1y++){VE vec{};auto begin1yx = I1y->begin(),end1yx = I1y->end();for(uint z = 0;z < Z;z++){auto I1yx = begin1yx;auto I2x = begin2x;T inner_product{};WH(I1yx != end1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(MO(vec));}RE MA(MO(M_prod));}TE IN MA operator*(CO MA& mat,CO T& scalar) { RE MA(mat) *= scalar; }TE IN MA operator*(CO T& scalar,CO MA& mat) { RE mat * scalar; }TE IN MA operator%(CO MA& mat,CO T& scalar) { RE MA(mat) %= scalar; }TE MA Transpose(CO MA& mat){CO TT& M = mat.GetTable();TT M_t{};auto beginy = M.begin();for(auto I1x = beginy->begin(),end1x = beginy->end();I1x != end1x;I1x++){M_t.push_back(VE());}for(auto Iy = beginy,endy = M.end();Iy != endy;Iy++){auto Iyx = Iy->begin(),endyx = Iy->end();auto I_ty = M_t.begin();WH(Iyx != endyx){I_ty->push_back(*Iyx);Iyx++;I_ty++;}}RE MA(M_t);}TE T Trace(CO MA& mat){int i = 0;T AN =0;CO TT& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){AN += (*Iy)[i];i++;}RE AN;} TE void SetMultipointEvaluation(CO PO& f,CO LI > >& point_tree,V& AN);TE IN void SetMultipointEvaluation(CO PO& f,CO V& point,V& AN) { LI > > pt{}; SetPointTree(point,pt); SetMultipointEvaluation(f,pt,AN); }TE void SetMultipointEvaluation(CO PO& f,CO LI > >& point_tree,V& AN){CO LI >& prod = point_tree.front();if(prod.empty()){RE;}LI > residue = {};CO PO& zero = PO::zero();residue.push_back(zero);residue.back() = f % prod.front();auto I_tree = point_tree.begin(),end_tree = point_tree.end();I_tree++;WH(I_tree != end_tree){auto I_residue = residue.begin(),end_residue = residue.end();auto I_node = I_tree->begin(),end_node = I_tree->end();WH(I_residue != end_residue){CO PO& f = *I_node;I_node++;if(I_node != end_node){*(residue.insert(I_residue,zero)) = *I_residue % f;*I_residue %= *I_node;I_node++;}I_residue++;}I_tree++;}for(auto I_residue = residue.begin(),end_residue = residue.end();I_residue != end_residue;I_residue++){AN.push_back((*I_residue)[0]);}RE;}TE void SetProductTree(LI >& product_tree){LI empty{};LI *p_node = &(product_tree.back());WH(p_node->SZ() > 1){product_tree.push_front(empty);LI& node_curr = product_tree.front();for(auto I = p_node->begin(),end = p_node->end();I != end;I++){ST CO T null{};node_curr.push_back(null);T& f = *I;I++;if(I == end){node_curr.back() = f;break;} else {node_curr.back() = f * *I;}}p_node = &node_curr;}RE;}TE void SetPointTree(CO V& point,LI > >& point_tree){ST CO LI > empty{};point_tree.push_front(empty);LI >& linear = point_tree.front();for(auto I = point.begin(),end = point.end();I != end;I++){ST CO PO x{ 1,PO::CO_one() };linear.push_back(x);linear.back()[0] -= *I;}SetProductTree(point_tree);RE;} #define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,POINT) point = VE(SAMPLE_NUM_MAX + 1); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ point[t] = POINT; } VE eval[Y][Y] = {}; for(uint y = 0;y < Y;y++){ CO VE >& M_ref_y = M_ref[y]; VE (&eval_y)[Y] = eval[y]; for(uint x = 0;x < Y;x++){ SetMultipointEvaluation(M_ref_y[x],point,eval_y[x]); } } VE > sample(SAMPLE_NUM_MAX + 1,MA::Zero()); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ VE >& sample_t_ref = sample[t].RefTable(); for(uint y = 0;y < Y;y++){ VE& sample_t_ref_y = sample_t_ref[y]; VE (&eval_y)[Y] = eval[y]; for(uint x = 0;x < Y;x++){ sample_t_ref_y[x] = eval_y[x][t]; } } } #define MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(REST_INTERVAL_LENGTH) VE > eval_odd{}; VE > eval_even{}; SetIntervalEvaluation(subinterval_num_max,subinterval_length / interval_length,REST_INTERVAL_LENGTH + subinterval_num_max + 1,sample,eval_odd); SetIntervalEvaluation(subinterval_num_max,T(subinterval_num_max + 1),REST_INTERVAL_LENGTH,sample,eval_even); for(uint t = 0;t <= subinterval_num_max;t++){ sample[t] = eval_odd[t] * sample[t]; } for(uint t = 0;t < REST_INTERVAL_LENGTH;t++){ sample.push_back(eval_odd[t + subinterval_num_max + 1] * eval_even[t]); } TE void SetIntervalEvaluation(C_UINT deg,CO T& t_start,C_UINT length,VE& eval){for(uint d = 0;d <= deg;d++){eval[d] *= PO::factorial_inverse(d);}VE v{};v.swap(eval);TRPO f{ deg + 1,MO(v) };ST PO exp_inv{};for(uint d = exp_inv.SZ();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO::factorial_inverse(d):- PO::factorial_inverse(d));}f *= exp_inv;f.ReMORedundantZero();uint deg_f = f.SZ();if(deg_f == 0){eval = VE(length,PO::CO_zero());RE;}f.SetTruncation(deg_f);deg_f--;for(uint d = 0;d <= deg_f;d++){f[d] *= PO::factorial(d);}uint deg_f_half = (deg_f + 1) / 2;for(uint d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);}PO exp_t_Mahler{};T t_Mahler = PO::CO_one();for(uint d = 0;d <= deg_f;d++){exp_t_Mahler[d] = PO::factorial_inverse(d) * t_Mahler;t_Mahler *= t_start - d;}f *= exp_t_Mahler;for(uint d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);}for(uint d = 0;d <= deg_f;d++){f[d] *= PO::factorial_inverse(d);}f.SetTruncation(length);ST PO exp{};for(uint d = exp.SZ();d < length;d++){exp[d] = PO::factorial_inverse(d);}f *= exp;for(uint d = 0;d < length;d++){f[d] *= PO::factorial(d);}f.swap(eval);RE;}TE void SetIntervalEvaluation(C_UINT deg,CO T& t_start,C_UINT length,CO VE >& sample,VE >& eval){eval = VE >(length,MA::Zero());VE sample_copy[Y][X] = {};for(uint t = 0;t <= deg;t++){CO VE >& table = sample[t].GetTable();for(uint y = 0;y < Y;y++){VE (&sample_copy_y)[X] = sample_copy[y];CO VE& table_y = table[y];for(uint x = 0;x < X;x++){sample_copy_y[x].push_back(table_y[x]);}}}for(uint y = 0;y < Y;y++){VE (&sample_copy_y)[X] = sample_copy[y];for(uint x = 0;x < X;x++){VE& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,length,sample_copy_yx);for(uint i = 0;i < length;i++){VE >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}}RE;}TE void SetPRecursiveMAAction(CO MA >& M,MA& v,C_UINT length){if(length == 0){RE;}CO VE > >& M_ref = M.GetTable();uint deg = 1;for(uint y = 0;y < Y;y++){CO VE>& M_ref_y = M_ref[y];for(uint x = 0;x < Y;x++){CO uint SZ = M_ref_y[x].SZ();if(deg < SZ){deg = SZ;}}}deg--;uint interval_length = 1;int exponent = 0;WH(interval_length * (interval_length * deg + 1) < length){interval_length *= 2;exponent++;}interval_length /= 2;exponent--;uint interval_num_max;uint t_rest_start;VE point{};if(interval_length > 0){interval_num_max = length / interval_length - 1;t_rest_start = interval_length * (interval_num_max + 1);uint subinterval_num_max = deg;T subinterval_length = PO::CO_one();SET_MA_MULTIPOINT_EVALUATION(subinterval_num_max,t * interval_length);for(int e = 1;e < exponent;e++){MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(subinterval_num_max);subinterval_num_max *= 2;subinterval_length *= 2;}uint rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(rest_interval_length);for(uint t = 0;t <= interval_num_max;t++){v = sample[t] * v;}} else {interval_num_max = t_rest_start = 0;}if(t_rest_start < length){uint rest_num_max = length - t_rest_start - 1;SET_MA_MULTIPOINT_EVALUATION(rest_num_max,t + t_rest_start);for(uint t = 0;t <= rest_num_max;t++){v = sample[t] * v;}}RE;} class Query{PU:ll m_N;ll m_K;int m_t;IN Query(CO ll& N = 0,CO ll& K = 0,int t = 0 ):m_N(N),m_K(K),m_t(t){}};IN bool OP<(CO Query& q1,CO Query& q2){ RE q1.m_K < q2.m_K; }using MOD = Mod

;using MODX = PO;class D{PU:MA<2,2,MODX> m_M;MODX m_pt;IN D() : m_M(),m_pt() {};IN D(MA<2,2,MODX>&& M,MODX&& pt):m_M(MO(M)) , m_pt(MO(pt)) {}IN D(CO D& d):m_M(d.m_M),m_pt(d.m_pt) {}IN D(D&& d):m_M(MO(d.m_M)),m_pt(MO(d.m_pt)) {}IN D& OP=(CO D& d) { m_M = d.m_M; m_pt = d.m_pt; RE *this; }IN D& OP=(D&& d) { m_M = MO(d.m_M); m_pt = MO(d.m_pt); RE *this; }IN D& OP*=(CO D& d) { m_M *= d.m_M; m_pt *= d.m_pt; RE *this; }};IN D OP*(CO D& d1,CO D& d2 ) { RE D(d1.m_M * d2.m_M,d1.m_pt * d2.m_pt); } int main() { UNTIE; CEXPR( int , bound_T , 100000 ); CIN_ASSERT( T , 1 , bound_T ); CEXPR( ll , bound_N , 1000000000000000000 ); CEXPR( ll , bound_K1 , bound_T ); CEXPR( ll , bound_K2 , bound_N ); CO MOD& CO_zero = MODX::CO_zero(); CO MOD& CO_one = MODX::CO_one(); MOD CO_two{ 2 }; MOD CO_two_inv{ ( P + 1 ) / 2 }; CO MODX& zero = MODX::zero(); MODX one{ 0 , CO_one }; MODX X{ 1 , CO_one }; MODX X2_minus_half{ 2 , - CO_two_inv }; MA<2,1,MOD> v{ CO_one , CO_zero }; if( T > 5 ){ static Query Q[bound_T]; FOR( t , 0 , T ){ CIN_ASSERT( Nt , 1 , bound_N ); CIN_ASSERT( Kt , 0 , min( Nt * 2 , bound_K1 ) ); Q[t] = Query( Nt , Kt , t ); } sort( Q , Q + T ); LI > d_prod{}; LI > over_M{}; d_prod.push_front( LI() ); over_M.push_front( LI() ); LI& d_prod_init = d_prod.front(); LI& over_M_init = over_M.front(); ll k_start = 0; FOR( t , 0 , T ){ Query& Qt = Q[t]; FOR( k , k_start , Qt.m_K ){ d_prod_init.push_front ( D( MA<2,2,MODX> { X * CO_two - CO_two * k , X * k + CO_two_inv * ( ( 1 - k ) * k ) , MODX( one ) , MODX( zero ) } , MODX( one ) ) ); over_M_init.push_front( 1 ); } d_prod_init.push_front( D( MA<2,2,MODX>( 1 ) , X - Qt.m_N ) ); over_M_init.push_front( 0 ); k_start = Qt.m_K; } SetProductTree( d_prod ); SetProductTree( over_M ); LI > residue{}; residue.push_front( MA<2,1,MODX>( 1 ) ); auto itr_d_prod = d_prod.begin() , end_d_prod = d_prod.end(); auto itr_over_M = over_M.begin(); itr_d_prod++; itr_over_M++; MA<2,1,MODX> null{}; null.m_M.clear(); while( itr_d_prod != end_d_prod ){ auto itr_d_prod_node = itr_d_prod->begin() , end_d_prod_node = itr_d_prod->end(); auto itr_over_M_node = itr_over_M->begin(); FOR_ITR( residue , itr_residue , end_residue ){ MODX& pt_node_curr = itr_d_prod_node->m_pt; int& over_M_node_curr = *itr_over_M_node; itr_d_prod_node++; itr_over_M_node++; if( itr_d_prod_node != end_d_prod_node ){ residue.insert( itr_residue , over_M_node_curr == 0 ? MO( ( itr_d_prod_node->m_M * *itr_residue ) %= pt_node_curr ) : MA<2,1,MODX>( null ) ); if( *itr_over_M_node == 0 ){ *itr_residue %= itr_d_prod_node->m_pt; } itr_d_prod_node++; itr_over_M_node++; } else { break; } } itr_d_prod++; itr_over_M++; } static ll answer[bound_T]; auto itr_over_M_node = over_M.back().begin(); auto itr_residue = residue.begin(); FOREQINV( t , T - 1 , 0 ){ while( *itr_over_M_node == 1 ){ itr_over_M_node++; itr_residue++; } answer[Q[t].m_t] = itr_residue->m_M[0][0][0].Represent(); itr_over_M_node++; itr_residue++; } FOR( t , 0 , T ){ cout << answer[t] << "\n"; } } else { REPEAT( T ){ CIN_ASSERT( N , 1 , bound_N ); CIN_ASSERT( K , 0 , min( N * 2 , bound_K2 ) ); if( K >= P ){ cout << 0 << "\n"; } else { MA<2,2,MODX> MNX { X * ( -CO_two ) + CO_two * N , X2_minus_half + X * ( CO_two_inv + N ) , MODX( one ) , MODX( zero ) }; MA<2,1,MOD> v_copy{ v }; SetPRecursiveMAAction( MNX , v_copy , K ); cout << v_copy.m_M[0][0] << "\n"; } } } QUIT; }