#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include using namespace std;using uint = unsigned int;using ll = long long; #define PU public #define PR PU #define TE template #define TY typename #define ST static #define IN inline #define OP operator #define CE constexpr #define CO const #define RE return #define NE noexcept #define VE vector #define LI list #define TYPE_OF(VAR) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio(false); cin.tie(nullptr) #define CEXPR(LL,BOUND,VALUE) CE CO 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_I(ARRAY,I,END) for(auto I = ARRAY .begin(),END = ARRAY .end();I != END;I ++) #define REPEAT(HOW_MANY_TIMES) FOR(VARIABLE_FOR_REPEAT,0,HOW_MANY_TIMES) #define QUIT RE 0 #define COUT(AN) cout << (AN) << "\n"; #define RETURN(AN) COUT(AN); QUIT TE IN T Residue(CO T& a,CO T& p){ RE a >= 0 ? a % p:p - (- a - 1) % p - 1; } #define RE_ZR_FOR_MU_FOR_TR_PO_IF( CD) if( CD){ RE OP=(zero); } #define RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF( CD) if( CD){ RE TRPO(m_N); } #define SET_VE_FOR_AN_OF_MU_FOR_TR_PO(N_OUTPUT_LIM) if(PO::m_size < N_OUTPUT_LIM){ for(uint i = PO::m_size;i < N_OUTPUT_LIM;i++){ PO::m_f.push_back(0); } PO::m_size = N_OUTPUT_LIM; } #define SET_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_PO(N_OUTPUT_LIM) VE answer(N_OUTPUT_LIM) #define SET_SUM_OF_MU_FOR_TR_PO PO::m_f[i] = sum #define SET_SUM_OF_TR_MU_CO_FOR_TR_PO answer[i] = sum #define SET_N_INPUT_START_FOR_MU_FOR_TR_PO(F,SIZE,N_INPUT_START_NUM) uint N_INPUT_START_NUM; for(uint i = 0;i < SIZE && SE;i++){ if(F[i] != zero){ N_INPUT_START_NUM = i; SE = false; } } #define SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(F,SIZE,N_INPUT_MAX_NUM) uint N_INPUT_MAX_NUM; SE = true; for(uint i = (SIZE) - 1;SE;i--){ if(F[i] != zero){ N_INPUT_MAX_NUM = i; SE = false; } } #define CONVOLUTION_FOR_MU_FOR_TR_PO(J_MIN) CO uint j_max = i < N_IPT_max_0_start_1 ? i - N_IPT_start_1:N_IPT_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_PO(J_MIN) CO uint j_max = i < N_IPT_max_0_start_1 ? i - N_IPT_start_1:N_IPT_max_0; T& m_fi = answer[i]; for(uint j = J_MIN;j <= j_max;j++){ m_fi += PO::m_f[j] * f.PO::m_f[i - j]; } #define ZN_FOR_MU_FOR_TR_PO for(uint i = 0;i < N_IPT_start_0_start_1;i++){ PO::m_f[i] = 0; } #define ZN_FOR_TR_MU_CO_FOR_TR_PO for(uint i = 0;i < N_IPT_start_0_start_1;i++){ answer[i] = 0; } #define CN(S1,S2) SUBSTITUTE_CN(S1,S2) #define SUBSTITUTE_CN(S1,S2) S1 ## S2 #define DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY) CN(CN(RE_ZR_FOR_,MU),_FOR_TR_PO_IF)(PO::m_size == 0); uint N_OPT_max = PO::m_size + f.PO::m_size - 2; if(N_OPT_max >= m_N){ N_OPT_max = m_N - 1; } CO uint N_OPT_lim = N_OPT_max + 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_PO)(N_OPT_lim); for(uint i = N_OPT_max;SE;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_PO); SE = i > 0; } #define DF_0_OF_MU_FOR_TR_PO DF_0_OF__FOR_TR_PO(MU,PO::m_f[j]) #define DF_0_OF_TR_MU_CO_FOR_TR_PO DF_0_OF__FOR_TR_PO(TR_MU_CO,PO::OP[](j)) #define DF_1_OF__FOR_TR_PO(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_PO(PO::m_f,PO::m_size,N_IPT_start_0); CN(CN(RE_ZR_FOR_,MU),_FOR_TR_PO_IF)(SE); SE = true; SET_N_INPUT_START_FOR_MU_FOR_TR_PO(f,f.PO::m_size,N_IPT_start_1); #define DF_1_OF_MU_FOR_TR_PO DF_1_OF__FOR_TR_PO(MU) #define DF_1_OF_TR_MU_CO_FOR_TR_PO DF_1_OF__FOR_TR_PO(TR_MU_CO) #define DF_2_OF_MU_FOR_TR_PO SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO::m_f,PO::m_size,N_IPT_max_0); SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO::m_size < m_N ? f.PO::m_size:m_N,N_IPT_max_1); CO uint N_IPT_max_0_max_1 = N_IPT_max_0 + N_IPT_max_1; CO uint N_IPT_start_0_start_1 = N_IPT_start_0 + N_IPT_start_1; #define DF_2_OF_TR_MU_CO_FOR_TR_PO DF_2_OF_MU_FOR_TR_PO #define DF_3_OF__FOR_TR_PO(MU) CO uint N_IPT_start_0_max_1 = N_IPT_start_0 + N_IPT_max_1; CO uint N_IPT_max_0_start_1 = N_IPT_max_0 + N_IPT_start_1; CO uint N_OPT_max_fixed = N_OPT_lim_fixed - 1; CN(CN(SET_VE_FOR_AN_OF_,MU),_FOR_TR_PO)(N_OPT_lim_fixed); for(uint i = N_OPT_max_fixed;i > N_IPT_start_0_max_1;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_PO)(i - N_IPT_max_1); } SE = true; for(uint i = N_IPT_start_0_max_1 < N_OPT_max_fixed ? N_IPT_start_0_max_1:N_OPT_max_fixed;SE;i--){ CN(CN(CONVOLUTION_FOR_,MU),_FOR_TR_PO)(N_IPT_start_0); SE = i > N_IPT_start_0_start_1; } CN(CN(ZN_FOR_,MU),_FOR_TR_PO); #define DF_3_OF_MU_FOR_TR_PO DF_3_OF__FOR_TR_PO(MU) #define DF_3_OF_TR_MU_CO_FOR_TR_PO DF_3_OF__FOR_TR_PO(TR_MU_CO) #define DF_4_OF_MU_FOR_TR_PO 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 }; while(N_IPT_truncated_deg_0_deg_1 >= two_power){ two_power *= 2; two_power_inv /= 2; exponent++; } VE f0{ move(FFT(PO::m_f,N_IPT_start_0,N_IPT_max_0 + 1,0,two_power,exponent)) }; CO VE f1{ move(FFT(f.PO::m_f,N_IPT_start_1,N_IPT_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_PO DF_4_OF_MU_FOR_TR_PO #define DF_OF_INVERSE_FOR_TR_PO(TYPE,RECURSION) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_inv{ power_2,PO< TYPE >::CO_one() / f[0] }; while(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_PO(TYPE,RECURSION) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TRPO< TYPE > f_exp{ power_2,PO< TYPE >::CO_one() }; while(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_PO(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_PO(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_PO(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_PO(TYPE) TE <> PO& PO::OP*=(CO PO& f) { if(m_size != 0){ VE v{}; v.swap(m_f); TRPO f_copy{ m_size + f.m_size - 1,move(v) }; f_copy *= f; m_f = move(f_copy.PO::m_f); m_size = m_f.size(); } RE *this; } #define SET_MATRIX_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,POINT) point = move(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_MATRIX(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] = move(eval_odd[t] * sample[t]); } for(uint t = 0;t < REST_INTERVAL_LENGTH;t++){ sample.push_back(move(eval_odd[t + subinterval_num_max + 1] * eval_even[t])); } #define PROD_MXK(K_START) FOR(k,K_START,K_lim){ MXk.push_front (move(MA<2,2,MODX> { X * CO_two - CO_two * k,X * k + CO_two_inv * ((1 - k) * k),one,zero })); } IN CEXPR(ll,P,998244353);TE class Mod{protected: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;while(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;while(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 size = p_inverse->size();for(ll i = size;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(); }TE class TRPO;TE class PO{friend class TRPO;protected:VE m_f;uint m_size;PU:IN PO();IN PO(CO T& t);IN PO(CO PO& f);IN PO(PO&& f);IN PO(CO uint& i,CO T& t);IN PO(VE&& f);PO& OP=(CO T& t);PO& OP=(CO PO& f);IN CO T& OP[](CO uint& i) CO;IN T& OP[](CO 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 CO uint& size() CO NE;IN void swap(PO& f);IN void swap(VE& f);void RemoveRedundantZero();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(CO uint& i);ST IN CO T& factorial_inverse(CO 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,CO uint& N_OPT_start_plus_one);TE TRPO TRIntegral(CO TRPO& f,CO uint& N_OPT_start);TE class TRPO;TE TRPO TRDifferential(CO TRPO& f,CO uint& N_OPT_start_plus_one);TE TRPO TRIntegral(CO TRPO& f,CO uint& N_OPT_start);TE class TRPO :PU PO{friend TRPO TRDifferential(CO TRPO& f,CO uint& N_OPT_start_plus_one);friend TRPO TRIntegral(CO TRPO& f,CO uint& N_OPT_start);PR:uint m_N;PU:IN TRPO(CO uint& N = 0);IN TRPO(CO TRPO& f);IN TRPO(CO uint& N,CO T& t);TRPO(CO uint& N,CO PO& f);IN TRPO(CO uint& N,PO&& f);IN TRPO(CO uint& N,CO uint& i,CO T& t);IN TRPO(CO uint& N,VE&& f);IN TRPO& OP=(CO TRPO& f);IN TRPO& OP=(CO T& t);IN TRPO& OP=(CO 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,CO uint& N_IPT_start,CO uint& N_IPT_limit);IN TRPO& OP-=(CO T& t);IN TRPO& OP-=(CO PO& f);IN TRPO& OP-=(CO TRPO& f);TRPO& TRMinus(CO PO& f,CO uint& N_IPT_start,CO uint& N_IPT_limit);IN TRPO& OP*=(CO T& t);TRPO& OP*=(CO PO& f);TRPO& FFT_MU(CO PO& f);TRPO& TRMU(CO PO& f,CO uint& N_IPT_start,CO uint& N_IPT_lim);TRPO& FFT_TRMU(CO PO& f,CO uint& N_IPT_start,CO uint& N_IPT_lim);TRPO TRMU_CO(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO;TRPO FFT_TRMU_CO(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_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(CO uint& N) NE;IN CO uint& GetTruncation() CO NE;IN TRPO& TruncateInitial(CO uint& N) NE;IN TRPO& TruncateFinal(CO 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(CO uint& i,CO TRPO& f);TE TRPO TRDifferential(CO TRPO& f,CO uint& N_OPT_start_plus_one);TE IN TRPO Integral(CO TRPO& f);TE TRPO TRIntegral(CO TRPO& f,CO uint& N_OPT_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,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent);TE IN VE FFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent);TE VE IFFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE VE IFFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE <> IN CE CO uint LimitOfPowerForFFT > = 24;TE <> IN CE CO uint BorderForFFT > = 4; TE <> IN CO Mod

(&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT >]{ST CO Mod

PRT[ LimitOfPowerForFFT > ] ={Mod

(1) ,Mod

(998244352) ,Mod

(911660635) ,Mod

(625715529) ,Mod

(373294451) ,Mod

(827987769) ,Mod

(280333251) ,Mod

(581015842) ,Mod

(628092333) ,Mod

(300892551) ,Mod

(586046298) ,Mod

(615001099) ,Mod

(318017948) ,Mod

(64341522) ,Mod

(106061068) ,Mod

(304605202) ,Mod

(631920086) ,Mod

(857779016) ,Mod

(841431251) ,Mod

(805775211) ,Mod

(390359979) ,Mod

(923521) ,Mod

(961) ,Mod

(31)};RE PRT;}TE <> IN CO Mod

(&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT >]{ST CO Mod

PRT[ LimitOfPowerForFFT > ] ={Mod

(1) ,Mod

(998244352) ,Mod

(86583718) ,Mod

(488723995) ,Mod

(369330050) ,Mod

(543653592) ,Mod

(382946991) ,Mod

(844956623) ,Mod

(91420391) ,Mod

(433414612) ,Mod

(288894979) ,Mod

(260490556) ,Mod

(857007890) ,Mod

(736054570) ,Mod

(474649464) ,Mod

(948509906) ,Mod

(114942468) ,Mod

(962405921) ,Mod

(667573957) ,Mod

(46809892) ,Mod

(304321983) ,Mod

(30429817) ,Mod

(293967900) ,Mod

(128805723)};RE PRT;}TE ST VE FFT_Body(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT]);TE ST VE FFT_Body(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT]);TE IN VE FFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power,exponent,0,1,PrimitiveRootOfTwoForFFT()); }TE IN VE FFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,N_OPT_start,N_OPT_lim,N_OPT_shift,two_power,exponent,PrimitiveRootOfTwoForFFT()); }TE VE IFFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE answer{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT())) };CO uint size = answer.size();for(uint i = 0;i < size;i++){answer[i] *= two_power_inv;}RE answer;}TE VE IFFT(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE answer{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,N_OPT_start,N_OPT_lim,N_OPT_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT())) };uint size = answer.size();CO uint N_OPT_length = N_OPT_lim - N_OPT_start + N_OPT_shift;if(size < N_OPT_length){size = N_OPT_length;}for(uint i = N_OPT_shift;i < size;i++){answer[i] *= two_power_inv;}RE answer;}TE ST VE FFT_Body(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& N_OPT_start,CO uint& N_OPT_lim,CO uint& N_OPT_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT]){CO uint length = N_OPT_lim - N_OPT_start + N_OPT_shift;VE answer(length);if(two_power == 1){if(N_IPT_shift == 0 && N_OPT_shift < length){if(N_IPT_start < N_IPT_lim){answer[N_OPT_shift] = f[N_IPT_start];}}} else {CO T& zeta = PRT[exponent];T zeta_power = PRT[0];uint N_OPT_start_copy = N_OPT_start;uint digit = 0;if(N_OPT_start_copy != 0){if(N_OPT_start_copy % 2 == 1){zeta_power *= zeta;}N_OPT_start_copy /= 2;digit++;}while(N_OPT_start_copy != 0){if(N_OPT_start_copy % 2 == 1){zeta_power *= PRT[exponent - digit];}N_OPT_start_copy /= 2;digit++;}CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;VE answer_sub0{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,0,2,PRT)) };VE answer_sub1{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,1,2,PRT)) };for(uint i = N_OPT_start;i < N_OPT_lim;i++){CO uint i_sub = i % two_power_sub;answer[i - N_OPT_start + N_OPT_shift] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];zeta_power *= zeta;}}RE answer;}TE ST VE FFT_Body(CO VE& f,CO uint& N_IPT_start,CO uint& N_IPT_lim,CO uint& N_IPT_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT]){VE answer(two_power);CO uint start_depth = start + ((two_power - 1) * depth);CO uint N_IPT_length = N_IPT_lim - N_IPT_start + N_IPT_shift;if(start < N_IPT_length && N_IPT_shift <= start_depth){uint j_min;if(start < N_IPT_shift){CO uint N_IPT_shift_shift = N_IPT_shift - start;j_min = N_IPT_shift_shift / depth + (N_IPT_shift_shift % depth == 0 ? 0:1);} else {j_min = 0;}uint j_lim;if(N_IPT_length <= start_depth){CO uint N_IPT_length_shift = N_IPT_length - start;j_lim = N_IPT_length_shift / depth + (N_IPT_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_IPT_shift + N_IPT_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 };while(j_hit != 0){if(j_hit % 2 == 1){zeta_power *= zeta_power_2;}zeta_power_2 *= zeta_power_2;j_hit /= 2;}answer[0] = f[index_hit];for(uint i = 1;i < two_power;i++){answer[i] = zeta_power * answer[i-1];}} else if(count > 1){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };CE CO uint& border = BorderForFFT;if(exponent < border){for(uint i = 0;i < two_power;i++){T& answer_i = answer[i];T zeta_power_power{ one };T zeta_power_power_2{ zeta_power };uint j_min_copy = j_min;while(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_IPT_shift + N_IPT_start;for(uint j = j_min;j < j_lim;j++){answer_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 answer_sub0{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_shift,two_power_sub,exponent_sub,start,depth_sub,PRT)) };VE answer_sub1{ move(FFT_Body(f,N_IPT_start,N_IPT_lim,N_IPT_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;answer[i] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];zeta_power *= zeta;}}}}RE answer;}TE IN TRPO::TRPO(CO uint& N):PO(),m_N(N) {}TE IN TRPO::TRPO(CO TRPO& f):PO(f),m_N(f.m_N) {}TE IN TRPO::TRPO(CO uint& N,CO T& t):PO(t),m_N(N) {}TE TRPO::TRPO(CO uint& N,CO PO& f):PO(),m_N(N){CO uint& size = f.PO::m_size < m_N ? f.PO::m_size:m_N;for(uint i = 0;i < size;i++){PO::m_f.push_back(f.PO::m_f[i]);PO::m_size++;}}TE IN TRPO::TRPO(CO uint& N,PO&& f):PO(move(f)),m_N(N) {};TE IN TRPO::TRPO(CO uint& N,CO 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(CO uint& N,VE&& f):PO(move(f)),m_N(N){while(PO::m_size > m_N){PO::m_f.pop_back();PO::m_size--;}}TE IN TRPO& TRPO::OP=(CO TRPO& f) { PO::OP=(f); m_N = 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+=(CO T& t) { PO::OP+=(t); RE *this; }TE IN TRPO& TRPO::OP+=(CO PO& f) { RE TRPO::TRPlus(f,0,f.PO::m_size); }TE IN TRPO& TRPO::OP+=(CO TRPO& f) { RE m_N == 0 ? OP=(f):TRPO::TRPlus(f,0,f.PO::m_size); }TE TRPO& TRPO::TRPlus(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_limit){CO uint& size = N_OPT_limit < m_N ? N_OPT_limit < f.PO::m_size ? N_OPT_limit:f.PO::m_size:m_N < f.PO::m_size ? m_N:f.PO::m_size;CO uint& size_min = PO::m_size < size ? PO::m_size:size;for(uint i = N_OPT_start;i < size_min;i++){PO::m_f[i] += f.PO::m_f[i];}for(uint i = PO::m_size;i < size;i++){PO::m_f.push_back(f.PO::m_f[i]);PO::m_size++;}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_size); }TE IN TRPO& TRPO::OP-=(CO TRPO& f) { RE m_N == 0 ? OP=(-f):TRPO::TRMinus(f,0,f.PO::m_size); }TE TRPO& TRPO::TRMinus(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_limit){CO uint& size = N_OPT_limit < m_N ? N_OPT_limit < f.PO::m_size ? N_OPT_limit:f.PO::m_size:m_N < f.PO::m_size ? m_N:f.PO::m_size;CO uint& size_min = PO::m_size < size ? PO::m_size:size;for(uint i = N_OPT_start;i < size_min;i++){PO::m_f[i] -= f.PO::m_f[i];}for(uint i = PO::m_size;i < size;i++){PO::m_f.push_back(- f.PO::m_f[i]);PO::m_size++;}RE *this;}TE IN TRPO& TRPO::OP*=(CO T& t) { PO::OP*=(t); RE *this; }DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_PO(Mod

,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 SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){RE_ZR_FOR_MU_FOR_TR_PO_IF(f.PO::m_size == 0);DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;RE_ZR_FOR_MU_FOR_TR_PO_IF(SE);DF_2_OF_MU_FOR_TR_PO;CO uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= m_N);DF_3_OF_MU_FOR_TR_PO;}RE *this;}TE TRPO& TRPO::FFT_MU(CO PO& f){CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){RE_ZR_FOR_MU_FOR_TR_PO_IF(f.PO::m_size == 0);DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;RE_ZR_FOR_MU_FOR_TR_PO_IF(SE);DF_2_OF_MU_FOR_TR_PO;CO uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_PO;} else {DF_4_OF_MU_FOR_TR_PO;PO::m_f = move(IFFT(f0,0,two_power,0,0,N_OPT_lim_fixed - N_IPT_start_0_start_1,N_IPT_start_0_start_1,two_power,two_power_inv,exponent));PO::m_size = PO::m_f.size();}}RE *this;}TE TRPO& TRPO::TRMU(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_lim){CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;DF_2_OF_MU_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);DF_3_OF_MU_FOR_TR_PO;}RE *this;}TE TRPO& TRPO::FFT_TRMU(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_lim){CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){DF_0_OF_MU_FOR_TR_PO;} else {DF_1_OF_MU_FOR_TR_PO;DF_2_OF_MU_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_MU_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_MU_FOR_TR_PO;} else {DF_4_OF_MU_FOR_TR_PO;uint N_OPT_start_shifted;uint N_OPT_shift_shifted;if(N_OPT_start < N_IPT_start_0_start_1){N_OPT_start_shifted = 0;N_OPT_shift_shifted = N_IPT_start_0_start_1;} else {N_OPT_start_shifted = N_OPT_start - N_IPT_start_0_start_1;N_OPT_shift_shifted = N_OPT_start;}CO uint N_OPT_lim_shifted = N_OPT_lim_fixed - N_IPT_start_0_start_1;f0 = move(IFFT(f0,0,two_power,0,N_OPT_start_shifted,N_OPT_lim_shifted,N_OPT_shift_shifted,two_power,two_power_inv,exponent));SET_VE_FOR_AN_OF_MU_FOR_TR_PO(N_OPT_lim_fixed);for(uint i = N_OPT_start;i < N_OPT_lim_fixed;i++){PO::m_f[i] = f0[i];}}}RE *this;}TE TRPO TRPO::TRMU_CO(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO{CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){DF_0_OF_TR_MU_CO_FOR_TR_PO;RE TRPO(m_N,move(answer));}DF_1_OF_TR_MU_CO_FOR_TR_PO;DF_2_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);DF_3_OF_TR_MU_CO_FOR_TR_PO;RE TRPO(m_N,move(answer));}TE TRPO TRPO::FFT_TRMU_CO(CO PO& f,CO uint& N_OPT_start,CO uint& N_OPT_lim) CO{CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool SE = true;if(PO::m_size < border_0 && f.PO::m_size < border_0){DF_0_OF_TR_MU_CO_FOR_TR_PO;RE TRPO(m_N,move(answer));}DF_1_OF_TR_MU_CO_FOR_TR_PO;DF_2_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_lim_fixed = N_IPT_max_0_max_1 < m_N ? N_IPT_max_0_max_1 + 1:m_N;if(N_OPT_lim_fixed > N_OPT_lim){N_OPT_lim_fixed = N_OPT_lim;}RE_ZR_FOR_TR_MU_CO_FOR_TR_PO_IF(N_IPT_start_0_start_1 >= N_OPT_lim_fixed);CO uint N_IPT_truncated_deg_0_deg_1 = N_IPT_max_0 - N_IPT_start_0 + N_IPT_max_1 - N_IPT_start_1;CE CO uint& border_1 = FFT_MU_border_1;if(N_IPT_truncated_deg_0_deg_1 < border_1){DF_3_OF_TR_MU_CO_FOR_TR_PO;RE TRPO(m_N,move(answer));}DF_4_OF_TR_MU_CO_FOR_TR_PO;uint N_OPT_start_shifted;uint N_OPT_shift_shifted;if(N_OPT_start < N_IPT_start_0_start_1){N_OPT_start_shifted = 0;N_OPT_shift_shifted = N_IPT_start_0_start_1;} else {N_OPT_start_shifted = N_OPT_start - N_IPT_start_0_start_1;N_OPT_shift_shifted = N_OPT_start;}CO uint N_OPT_lim_shifted = N_OPT_lim_fixed - N_IPT_start_0_start_1;RE TRPO(m_N,move(IFFT(f0,0,two_power,0,N_OPT_start_shifted,N_OPT_lim_shifted,N_OPT_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(CO uint& N) NE { m_N = N; TruncateFinal(m_N); }TE IN CO uint& TRPO::GetTruncation() CO NE { RE m_N; }TE IN TRPO& TRPO::TruncateInitial(CO uint& N) NE { CO uint& size = N < PO::m_size ? N:PO::m_size; for(uint i = 0;i < size;i++){ PO::m_f[i] = 0; } RE *this; }TE IN TRPO& TRPO::TruncateFinal(CO uint& N) NE { while(PO::m_size > N){ PO::m_f.pop_back(); PO::m_size--; } 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(CO uint& i,CO TRPO& f) { RE i == 0 ? f:Differential(i - 1,Differential(f)); }TE TRPO TRDifferential(CO TRPO& f,CO uint& N_OPT_start_plus_one){if(f.m_N == 0){RE TRPO();}TRPO f_dif{ f.m_N - 1 };if(N_OPT_start_plus_one < f.PO::m_size){for(uint i = 1;i < N_OPT_start_plus_one;i++){f_dif.PO::m_f.push_back(0);}for(uint i = N_OPT_start_plus_one;i < f.PO::m_size;i++){f_dif.PO::m_f.push_back(i * f.PO::m_f[i]);}f_dif.PO::m_size = f.PO::m_size - 1;}RE f_dif;}TE IN TRPO Integral(CO TRPO& f) { RE TRIntegral(f,1); }TE TRPO TRIntegral(CO TRPO& f,CO uint& N_OPT_start){TRPO f_int{ f.m_N + 1 };if(N_OPT_start <= f.PO::m_size){for(uint i = 0;i < N_OPT_start;i++){f_int.PO::m_f.push_back(0);}for(uint i = N_OPT_start;i <= f.PO::m_size;i++){f_int.PO::m_f.push_back(f.PO::m_f[i - 1] / T(i));}f_int.PO::m_size = f.PO::m_size + 1;}RE f_int;}TE TRPO Inverse(CO TRPO& f){DF_OF_INVERSE_FOR_TR_PO(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_PO(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_size(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_size(f.m_size) {}TE IN PO::PO(PO&& f):m_f(move(f.m_f)),m_size(move(f.m_size)) {}TE IN PO::PO(CO uint& i,CO T& t):PO() { if(t != CO_zero()){ OP[](i) = t; } }TE IN PO::PO(VE&& f):m_f(move(f)),m_size(m_f.size()) {}TE IN PO& PO::OP=(CO T& t) { m_f.clear(); m_size = 0; OP[](0) = t; RE *this; }TE IN PO& PO::OP=(CO PO& f) { m_f = f.m_f; m_size = f.m_size; RE *this; }TE CO T& PO::OP[](CO uint& i) CO{if(m_size <= i){RE CO_zero();}RE m_f[i];}TE IN T& PO::OP[](CO uint& i){if(m_size <= i){CO T& z = CO_zero();while(m_size <= i){m_f.push_back(z);m_size++;}}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_size;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_size;i++){OP[](i) -= f.m_f[i];}RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(Mod

);TE PO& PO::OP*=(CO T& t){if(m_size == 0 || t == CO_one()){RE *this;}if(t == CO_zero()){RE OP=(zero());}for(uint i = 0;i < m_size;i++){OP[](i) *= t;}RE *this;}TE PO& PO::OP*=(CO PO& f){if(m_size == 0){RE *this;}if(f.m_size == 0){RE OP=(zero());}CO uint size = m_size + f.m_size - 1;PO product{}; for(uint i = 0;i < size;i++){T& product_i = product[i];CO uint j_min = m_size <= i ? i - m_size + 1:0;CO uint j_lim = i < f.m_size ? i + 1:f.m_size;for(uint j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(move(product));}TE PO& PO::OP/=(CO T& t){if(t == CO_one()){RE *this;}for(uint i = 0;i < m_size;i++){OP[](i) /= t;}RE *this;}TE PO& PO::OP/=(CO PO& f){if(m_size >= f.m_size){assert(f.m_size > 0);uint size0 = m_size - f.m_size + 1;TRPO f0_copy(size0);for(uint d0 = 0;d0 < size0;d0++){f0_copy.PO::m_f.push_back(m_f[m_size - 1 - d0]);}f0_copy.PO::m_size = size0;TRPO f1_copy(size0);uint size1 = size0 < f.m_size ? size0:f.m_size;for(uint d1 = 0;d1 < size1;d1++){f1_copy.PO::m_f.push_back(f.m_f[f.m_size - 1 - d1]);}f1_copy.PO::m_size = size1;f0_copy /= f1_copy;for(uint d0 = 0;d0 < size0;d0++){m_f[d0] = f0_copy[ size0 - 1 - d0 ];}while(m_size > size0){m_f.pop_back();m_size--;}} else {PO::m_f.clear();PO::m_size = 0;}RE *this;}TE PO& PO::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(uint i = 0;i < m_size;i++){OP[](i) %= t;}RE *this;}TE PO& PO::OP%=(CO PO& f){if(m_size >= f.m_size){OP-=((*this / f) * f);RemoveRedundantZero();}RE *this;}TE IN PO PO::OP-() CO { RE PO().OP-=(*this); }TE PO& PO::OP<<=(CO T& t){if(m_size > 0){ST T factorial_curr = 1;ST VE factorial = { 1,1 };ST T factorial_inv_curr = 1;ST VE factorial_inv = { 1,1 };uint size = factorial.size();while(size < m_size){factorial.push_back(factorial_curr *= size);factorial_inv.push_back(factorial_inv_curr /= size);size++;}for(uint d = 0;d < m_size;d++){m_f[d] *= factorial[d];}TRPO f{ m_size * 2 };T power_t = CO_one();for(uint d = 0;d < m_size;d++){f[m_size - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for(uint d = 0;d < m_size;d++){m_f[d] = f.PO::m_f[d + m_size - 1] * factorial_inv[d];}}RE *this;}TE IN CO VE& PO::GetCoefficient() CO NE { RE m_f; }TE IN CO uint& PO::size() CO NE { RE m_size; }TE IN void PO::swap(PO& f) { m_f.swap(f.m_f); swap(m_size,f.m_size); }TE IN void PO::swap(VE& f) { m_f.swap(f); m_size = m_f.size(); }TE void PO::RemoveRedundantZero(){CO T& z = CO_zero();while(m_size > 0 ? m_f[m_size - 1] == z:false){m_f.pop_back();m_size--;}RE;}TE string PO::Display() CO NE{string s = "(";if(m_size > 0){s += to_string(m_f[0]);for(uint i = 1;i < m_size;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(CO uint& i) { ST VE memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint size = 2; while(size <= i){ memory.push_back(curr *= size++); } RE memory[i]; }TE IN CO T& PO::factorial_inverse(CO uint& i) { ST VE memory = { CO_one(),CO_one() }; ST T curr = CO_one(); ST uint size = 2; while(size <= i){ memory.push_back(curr /= size++); } RE memory[i]; }TE bool OP==(CO PO& f0,CO T& t1){CO uint& size = f0.size();CO T& zero = PO::CO_zero();for(uint i = 1;i < size;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE bool OP==(CO PO& f0,CO PO& f1){CO uint& size0 = f0.size();CO uint& size1 = f1.size();CO uint& size = size0 < size1 ? size1:size0;for(uint i = 0;i < size;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.size() == 1){RE f.front();}auto I = f.begin(),end = f.end();while(I != end){T& t = *I;I++;if(I != end){t = t * *I;I = f.erase(I);}}RE Prod(f);}TE IN void SetMultipointEvaluation(CO PO& f,CO V& point,V& answer);TE void SetMultipointEvaluation(CO PO& f,CO LI > >& point_tree,V& answer);TE IN void SetMultipointEvaluation(CO PO& f,CO LI& point,LI& answer);TE void SetProductTree(LI >& product_tree);TE void SetPointTree(CO V& point,LI > >& point_tree);TE IN void SetMultipointEvaluation(CO PO& f,CO V& point,V& answer) { LI > > pt{}; SetPointTree(point,pt); SetMultipointEvaluation(f,pt,answer); }TE void SetMultipointEvaluation(CO PO& f,CO LI > >& point_tree,V& answer){CO LI >& prod = point_tree.front();if(prod.empty()){RE;}LI > residue = {};CO PO& zero = PO::zero();residue.push_back(zero);residue.back() = move(f % prod.front());auto I_tree = point_tree.begin(),end_tree = point_tree.end();I_tree++;while(I_tree != end_tree){auto I_residue = residue.begin(),end_residue = residue.end();auto I_node = I_tree->begin(),end_node = I_tree->end();while(I_residue != end_residue){CO PO& f = *I_node;I_node++;if(I_node != end_node){*(residue.insert(I_residue,zero)) = move(*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++){answer.push_back((*I_residue)[0]);}RE;}TE void SetProductTree(LI >& product_tree){LI empty{};LI *p_node = &(product_tree.back());while(p_node->size() > 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() = move(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;}TE using TableTypeForMA = VE >;TE class MA{PR:TableTypeForMA m_M;PU:IN MA(CO T& t) NE;IN MA(CO int& t) NE;TE MA(CO Args&... args) NE;IN MA(CO MA& mat) NE;IN MA(MA&& mat) NE;TE IN MA(CO TableTypeForMA& M) NE;TE IN MA(TableTypeForMA&& M) NE;IN MA& operator=(CO 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 TableTypeForMA& RefTable() NE;IN CO TableTypeForMA& 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(TableTypeForMA& M,VE& vec) NE;TE ST void COructTable(TableTypeForMA& M,VE& vec,CO T& t,CO 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=(move(Scalar(t))); }TE IN MA::MA(CO int& t) NE:MA(T(1)) {}TE TE MA::MA(CO Args&... args) NE: m_M(){VE vec{};COructTable(m_M,vec,args...);}TE IN MA::MA(CO MA& mat) NE:m_M(mat.m_M) {}TE IN MA::MA(MA&& mat) NE:m_M(move(mat.m_M)) {}TE TE IN MA::MA(CO TableTypeForMA& M) NE:m_M(M) {}TE TE IN MA::MA(TableTypeForMA&& M) NE:m_M(move(M)) {}TE IN MA& MA::operator=(CO MA& mat) NE { m_M = 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(); while(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); while(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(); while(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin(); while(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=(move(*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 TableTypeForMA& MA::RefTable() NE { RE m_M; }TE IN CO TableTypeForMA& MA::GetTable() CO NE { RE m_M; }TE IN CO MA& MA::Zero() NE { ST CO MA zero = move(Zero_Body()); RE zero; }TE IN CO MA& MA::Unit() NE { ST CO MA unit = move(Scalar(T(1))); RE unit; }TE MA MA::Zero_Body() NE{VE vec(X);TableTypeForMA M(Y,vec);RE MA(move(M));}TE MA MA::Scalar(CO T& t) NE{MA M{ move(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(TableTypeForMA& M,VE& vec) NE { M.push_back(move(vec)); }TE TE void MA::COructTable(TableTypeForMA& M,VE& vec,CO T& t,CO Args&... args) NE{vec.push_back(t);if(vec.size() == X){VE v{};v.swap(vec);COructTable(M,v);}if(M.size() < Y){COructTable(M,vec,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 TableTypeForMA& M1 = mat1.GetTable();CO TableTypeForMA& M2 = mat2.GetTable();TableTypeForMA 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{};while(I1yx != end1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(move(vec));}RE MA(move(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 TableTypeForMA& M = mat.GetTable();TableTypeForMA 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();while(Iyx != endyx){I_ty->push_back(*Iyx);Iyx++;I_ty++;}}RE MA(M_t);}TE T Trace(CO MA& mat){int i = 0;T answer =0;CO TableTypeForMA& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){answer += (*Iy)[i];i++;}RE answer;}TE void SetIntervalEvaluation(CO uint& deg,CO T& t_start,CO 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,move(v) };ST PO exp_inv{};for(uint d = exp_inv.size();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO::factorial_inverse(d):- PO::factorial_inverse(d));}f *= exp_inv;f.RemoveRedundantZero();uint deg_f = f.size();if(deg_f == 0){eval = move(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.size();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(CO uint& deg,CO T& t_start,CO uint& length,CO VE >& sample,VE >& eval){eval = move(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,CO 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 size = M_ref_y[x].size();if(deg < size){deg = size;} }}deg--;uint interval_length = 1;int exponent = 0;while(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_MATRIX_MULTIPOINT_EVALUATION(subinterval_num_max,t * interval_length);for(int e = 1;e < exponent;e++){MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MATRIX(subinterval_num_max);subinterval_num_max *= 2;subinterval_length *= 2;}uint rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MATRIX(rest_interval_length);for(uint t = 0;t <= interval_num_max;t++){v = move(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_MATRIX_MULTIPOINT_EVALUATION(rest_num_max,t + t_rest_start);for(uint t = 0;t <= rest_num_max;t++){v = move(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 operator<(CO Query& q1,CO Query& q2) { RE q1.m_K > q2.m_K; }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);using MOD = Mod

;using MODX = PO;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){ST 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);ll K_lim = Q[0].m_K;LI > > MXk_prod{};MXk_prod.push_front(LI >());LI >& MXk_prod_init = MXk_prod.front();LI point{};LI > MXk{};FOR(t,0,T){Query& Qt = Q[t];PROD_MXK(Qt.m_K);MXk_prod_init.push_back(move(Prod(MXk)));point.push_back(Qt.m_N);K_lim = Qt.m_K;MXk.clear();}SetProductTree(MXk_prod);LI > pt{};SetPointTree(point,pt);auto I_pt = pt.begin();LI > residue{};PROD_MXK(0);residue.push_front(move(Prod(MXk) %= I_pt->front()));I_pt++;auto I_MXk_prod = MXk_prod.begin(),end_MXk_prod = MXk_prod.end();I_MXk_prod++;while(I_MXk_prod != end_MXk_prod){auto I_MXk_prod_node = I_MXk_prod->begin(),end_MXk_prod_node = I_MXk_prod->end();auto I_pt_node = I_pt->begin();FOR_I(residue,I_residue,end_residue){I_MXk_prod_node++;if(I_MXk_prod_node != end_MXk_prod_node){MODX& pt_node_curr = *I_pt_node;residue.insert(I_residue,move(((*I_MXk_prod_node %= pt_node_curr) * (*I_residue % pt_node_curr)) %= pt_node_curr));I_pt_node++;*I_residue %= *I_pt_node;I_MXk_prod_node++;I_pt_node++;} else {break;}}I_MXk_prod++;I_pt++;}ST ll answer[bound_T];auto I_residue = residue.begin();FOR(t,0,T){CO VE >& residue_t = I_residue->m_M;CO VE& residue_t_0 = residue_t[0];CO VE& residue_t_1 = residue_t[1];MA<2,2,MOD> residue_t_val{residue_t_0[0][0],residue_t_0[1][0] ,residue_t_1[0][0],residue_t_1[1][0]};answer[Q[t].m_t] = (residue_t_val * v).m_M[0][0].Represent();I_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) ,one,zero};MA<2,1,MOD> v_copy{ v };SetPRecursiveMAAction(MNX,v_copy,K);cout << v_copy.m_M[0][0] << "\n";}}}QUIT;}