結果

問題 No.2166 Paint and Fill
ユーザー 👑 p-adicp-adic
提出日時 2022-12-23 21:35:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 63,959 bytes
コンパイル時間 7,079 ms
コンパイル使用メモリ 304,312 KB
実行使用メモリ 701,260 KB
最終ジャッジ日時 2024-11-18 04:27:50
合計ジャッジ時間 196,216 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
428,020 KB
testcase_01 RE -
testcase_02 MLE -
testcase_03 AC 105 ms
425,284 KB
testcase_04 AC 104 ms
422,516 KB
testcase_05 AC 102 ms
431,264 KB
testcase_06 AC 106 ms
431,428 KB
testcase_07 AC 103 ms
424,628 KB
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
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 SZ size
#define WH while
#define TYPE_OF(VAR) remove_const<remove_reference<decltype(VAR)>::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 
#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<T>(m_N); } 
#define SET_VE_FOR_AN_OF_MU_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) if(PO<T>::m_SZ < N_OUTPUT_LIM){ for(uint i = PO<T>::m_SZ;i < N_OUTPUT_LIM;i++){ PO<T>::m_f.push_back(0); } PO<T>::m_SZ = N_OUTPUT_LIM; } 
#define SET_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_POLYNOMIAL(N_OUTPUT_LIM) VE<T> AN(N_OUTPUT_LIM) 
#define SET_SUM_OF_MU_FOR_TR_POLYNOMIAL PO<T>::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<T>::m_f[j] * f.PO<T>::m_f[i - j]; } PO<T>::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<T>::m_f[j] * f.PO<T>::m_f[i - j]; } 
#define ZEROIFICATION_FOR_MU_FOR_TR_POLYNOMIAL for(uint i = 0;i < N_input_start_0_start_1;i++){ PO<T>::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<T>::m_SZ == 0); uint N_output_max = PO<T>::m_SZ + f.PO<T>::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<T>::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<T>::m_f[j]) 
#define DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL DF_0_OF__FOR_TR_POLYNOMIAL(TR_MU_CO,PO<T>::OP[](j)) 
#define DF_1_OF__FOR_TR_POLYNOMIAL(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_POLYNOMIAL(PO<T>::m_f,PO<T>::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<T>::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<T>::m_f,PO<T>::m_SZ,N_input_max_0); SET_N_INPUT_MAX_FOR_MU_FOR_TR_POLYNOMIAL(f,f.PO<T>::m_SZ < m_N ? f.PO<T>::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<T>; uint exponent = FFT_MU_border_1_2_exponent<T>; T two_power_inv{ FFT_MU_border_1_2_inv<T> }; WH(N_input_truncated_deg_0_deg_1 >= two_power){ two_power *= 2; two_power_inv /= 2; exponent++; } VE<T> f0{ move(FFT<T>(PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,0,two_power,exponent)) }; CO VE<T> f1{ move(FFT<T>(f.PO<T>::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) CO 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) CO 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<TYPE>& PO<TYPE>::OP*=(CO PO<TYPE>& f) { if(m_SZ != 0){ VE<TYPE> v{}; v.swap(m_f); TRPO<TYPE> f_copy{ m_SZ + f.m_SZ - 1,move(v) }; f_copy *= f; m_f = move(f_copy.PO<TYPE>::m_f); m_SZ = m_f.SZ(); } RE *this; }
#define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,POINT) point = move(VE<T>(SAMPLE_NUM_MAX + 1)); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ point[t] = POINT; } VE<T> eval[Y][Y] = {}; for(uint y = 0;y < Y;y++){ CO VE<PO<T> >& M_ref_y = M_ref[y]; VE<T> (&eval_y)[Y] = eval[y]; for(uint x = 0;x < Y;x++){ SetMultipointEvaluation(M_ref_y[x],point,eval_y[x]); } } VE<MA<Y,Y,T> > sample(SAMPLE_NUM_MAX + 1,MA<Y,Y,T>::Zero()); for(uint t = 0;t <= SAMPLE_NUM_MAX;t++){ VE<VE<T> >& sample_t_ref = sample[t].RefTable(); for(uint y = 0;y < Y;y++){ VE<T>& sample_t_ref_y = sample_t_ref[y]; VE<T> (&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<MA<Y,Y,T> > eval_odd{}; VE<MA<Y,Y,T> > 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])); }
TE <TY T> IN T Residue(CO T& a,CO T& p){ RE a >= 0 ? a % p:p - (- a - 1) % p - 1; }IN CEXPR(ll,P,998244353);TE <ll M>class Mod{PR:ll m_n;ll m_inv;PU:IN Mod() NE;IN Mod(CO ll& n) NE;IN Mod(CO Mod<M>& n) NE;IN Mod<M>& OP=(CO ll& n) NE;Mod<M>& OP=(CO Mod<M>& n) NE;Mod<M>& OP+=(CO ll& n) NE;IN Mod<M>& OP+=(CO Mod<M>& n) NE;IN Mod<M>& OP-=(CO ll& n) NE;IN Mod<M>& OP-=(CO Mod<M>& n) NE;Mod<M>& OP*=(CO ll& n) NE;Mod<M>& OP*=(CO Mod<M>& n) NE;virtual Mod<M>& OP/=(CO ll& n);virtual Mod<M>& OP/=(CO Mod<M>& n);Mod<M>& OP%=(CO ll& n);IN Mod<M>& OP%=(CO Mod<M>& n);IN Mod<M> OP-() CO NE;IN Mod<M>& OP++() NE;IN Mod<M>& OP++(int) NE;IN Mod<M>& OP--() NE;IN Mod<M>& 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 <ll M> IN bool OP==(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP==(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP!=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP<(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP<=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP>(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> IN bool OP>=(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP+(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP+(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP+(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP-(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP-(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP*(CO Mod<M>& n0,CO ll& n1) NE;TE <ll M> Mod<M> OP*(CO ll& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP*(CO Mod<M>& n0,CO Mod<M>& n1) NE;TE <ll M> Mod<M> OP/(CO Mod<M>& n0,CO ll& n1);TE <ll M> Mod<M> OP/(CO ll& n0,CO Mod<M>& n1);TE <ll M> Mod<M> OP/(CO Mod<M>& n0,CO Mod<M>& n1);TE <ll M> Mod<M> OP%(CO Mod<M>& n0,CO ll& n1);TE <ll M> IN Mod<M> OP%(CO ll& n0,CO Mod<M>& n1);TE <ll M> IN Mod<M> OP%(CO Mod<M>& n0,CO Mod<M>& n1);TE <ll M> Mod<M> Inverse(CO Mod<M>& n);TE <ll M> Mod<M> Power(CO Mod<M>& n,CO ll& p,CO string& method = "normal");TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method);TE <ll M> IN Mod<M> Power(CO Mod<M>& n,CO Mod<M>& p,CO string& method = "normal");TE <> IN Mod<2> Power(CO Mod<2>& n,CO Mod<2>& p,CO string& method);TE <TY T> IN T Square(CO T& t);TE <> IN Mod<2> Square<Mod<2> >(CO Mod<2>& t);TE <ll M> IN string to_string(CO Mod<M>& n) NE;TE<ll M,class Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& 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<ll> memory_M{};ST LI<VE<ll> > memory_inverse{};auto I_M = memory_M.begin(),end_M = memory_M.end();auto I_inverse = memory_inverse.begin();VE<ll>* 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<ll>());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 <ll M> IN Mod<M>::Mod() NE:m_n(0),m_inv(M){}TE <ll M> IN Mod<M>::Mod(CO ll& n) NE:m_n(Residue<ll>(n,M)),m_inv(0){}TE <ll M> IN Mod<M>::Mod(CO Mod<M>& n) NE:m_n(n.m_n),m_inv(0){}TE <ll M> IN Mod<M>& Mod<M>::OP=(CO ll& n) NE { RE OP=(Mod<M>(n)); }TE <ll M>Mod<M>& Mod<M>::OP=(CO Mod<M>& n) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP+=(CO ll& n) NE{m_n = Residue<ll>(m_n + n,M);m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP+=(CO Mod<M>& n) NE { RE OP+=(n.m_n); };TE <ll M> IN Mod<M>& Mod<M>::OP-=(CO ll& n) NE { RE OP+=(-n); }TE <ll M> IN Mod<M>& Mod<M>::OP-=(CO Mod<M>& n) NE { RE OP-=(n.m_n); }TE <ll M>Mod<M>& Mod<M>::OP*=(CO ll& n) NE{m_n = Residue<ll>(m_n * n,M);m_inv = 0;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP*=(CO Mod<M>& n) NE{m_n = Residue<ll>(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<ll>(m_inv * n.m_inv,M);}RE *this;}TE <ll M>Mod<M>& Mod<M>::OP/=(CO ll& n){RE OP/=(Mod<M>(n));}TE <ll M>Mod<M>& Mod<M>::OP/=(CO Mod<M>& n){RE OP*=(Inverse(n));}TE <ll M>Mod<M>& Mod<M>::OP%=(CO ll& n){m_n %= Residue<ll>(n,M);m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP%=(CO Mod<M>& n) { RE OP%=(n.m_n); }TE <ll M> IN Mod<M> Mod<M>::OP-() CO NE { RE Mod<M>(0).OP-=(*this); }TE <ll M> IN Mod<M>& Mod<M>::OP++() NE { RE OP+=(1); }TE <ll M> IN Mod<M>& Mod<M>::OP++(int) NE { RE OP++(); }TE <ll M> IN Mod<M>& Mod<M>::OP--() NE { RE OP-=(1); }TE <ll M> IN Mod<M>& Mod<M>::OP--(int) NE { RE OP-=(); }TE <ll M> IN CO ll& Mod<M>::Represent() CO NE { RE m_n; }TE <ll M>void Mod<M>::Invert() NE{if(CheckInvertible()){ll i = m_inv;m_inv = m_n;m_n = i;} else {m_n = M;m_inv = M;}RE;}TE <ll M>bool Mod<M>::CheckInvertible() NE{if(m_inv == 0){LazyEvaluationOfModularInverse(M,m_n,m_inv);}RE m_inv != M;}TE <ll M> IN bool Mod<M>::IsSmallerThan(CO ll& n) CO NE { RE m_n < Residue<ll>(n,M); }TE <ll M> IN bool Mod<M>::IsBiggerThan(CO ll& n) CO NE { RE m_n > Residue<ll>(n,M); }TE <ll M> IN bool OP==(CO Mod<M>& n0,CO ll& n1) NE { RE n0 == Mod<M>(n1); }TE <ll M> IN bool OP==(CO ll& n0,CO Mod<M>& n1) NE { RE Mod<M>(n0) == n0; }TE <ll M> IN bool OP==(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0.Represent() == n1.Represent(); }TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP!=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP!=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n0 == n1); }TE <ll M> IN bool OP<(CO Mod<M>& n0,CO ll& n1) NE { RE n0.IsSmallerThan(n1); }TE <ll M> IN bool OP<(CO ll& n0,CO Mod<M>& n1) NE { RE n1.IsBiggerThan(n0); }TE <ll M> IN bool OP<(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0.Represent() < n1.Represent(); }TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP<=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP<=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n1 < n0); }TE <ll M> IN bool OP>(CO Mod<M>& n0,CO ll& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>(CO ll& n0,CO Mod<M>& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n1 < n0; }TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO ll& n1) NE { RE !(n0 < n1); }TE <ll M> IN bool OP>=(CO ll& n0,CO Mod<M>& n1) NE { RE !(n0 < n1); }TE <ll M> IN bool OP>=(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE !(n0 < n1); }TE <ll M>Mod<M> OP+(CO Mod<M>& n0,CO ll& n1) NE{auto n = n0;n += n1;RE n;}TE <ll M> IN Mod<M> OP+(CO ll& n0,CO Mod<M>& n1) NE { RE n1 + n0; }TE <ll M> IN Mod<M> OP+(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0 + n1.Represent(); }TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO ll& n1) NE { RE n0 + (-n1); }TE <ll M> IN Mod<M> OP-(CO ll& n0,CO Mod<M>& n1) NE { RE Mod<M>(n0 - n1.Represent()); }TE <ll M> IN Mod<M> OP-(CO Mod<M>& n0,CO Mod<M>& n1) NE { RE n0 - n1.Represent(); }TE <ll M>Mod<M> OP*(CO Mod<M>& n0,CO ll& n1) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP*(CO ll& n0,CO Mod<M>& n1) NE { RE n1 * n0; }TE <ll M>Mod<M> OP*(CO Mod<M>& n0,CO Mod<M>& n1) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP/(CO Mod<M>& n0,CO ll& n1) { RE n0 / Mod<M>(n1); }TE <ll M> IN Mod<M> OP/(CO ll& n0,CO Mod<M>& n1) { RE Mod<M>(n0) / n1; }TE <ll M>Mod<M> OP/(CO Mod<M>& n0,CO Mod<M>& n1){auto n = n0;n /= n1;RE n;}TE <ll M>Mod<M> OP%(CO Mod<M>& n0,CO ll& n1){auto n = n0;n %= n1;RE n;}TE <ll M> IN Mod<M> OP%(CO ll& n0,CO Mod<M>& n1) { RE Mod<M>(n0) % n1.Represent(); }TE <ll M> IN Mod<M> OP%(CO Mod<M>& n0,CO Mod<M>& n1) { RE n0 % n1.Represent(); }TE <ll M>Mod<M> Inverse(CO Mod<M>& n){auto n_copy = n;n_copy.Invert();RE n_copy;}TE <ll M>Mod<M> Power(CO Mod<M>& n,CO ll& p,CO string& method){if(p >= 0){RE Power<Mod<M>,ll>(n,p,1,true,true,method);}RE Inverse(Power<M>(n,-p,method));}TE <> IN Mod<2> Power(CO Mod<2>& n,CO ll& p,CO string& method) { RE p == 0 ? 1:n; }TE <ll M> IN Mod<M> Power(CO Mod<M>& n,CO Mod<M>& p,CO string& method) { RE Power<Mod<M>,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<Mod<2> >(CO Mod<2>& t) { RE t; }TE <ll M> IN string to_string(CO Mod<M>& n) NE { RE to_string(n.Represent()) + " + MZ"; }TE<ll M,class Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n) { RE os << n.Represent(); }TE <TY T> class TRPO;TE <TY T>class PO{friend class TRPO<T>;PR:VE<T> m_f;uint m_SZ;PU:IN PO();IN PO(CO T& t);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(CO uint& i,CO T& t);IN PO(VE<T>&& f);PO<T>& OP=(CO T& t);PO<T>& OP=(CO PO<T>& f);IN CO T& OP[](CO uint& i) CO;IN T& OP[](CO uint& i);IN T OP()(CO T& t) CO;IN PO<T>& OP+=(CO T& t);PO<T>& OP+=(CO PO<T>& f);IN PO<T>& OP-=(CO T& t);PO<T>& OP-=(CO PO<T>& f);PO<T>& OP*=(CO T& t);PO<T>& OP*=(CO PO<T>& f);PO<T>& OP/=(CO T& t);PO<T>& OP/=(CO PO<T>& f);PO<T>& OP%=(CO T& t);PO<T>& OP%=(CO PO<T>& f);IN PO<T> OP-() CO;PO<T>& OP<<=(CO T& t);IN CO VE<T>& GetCoefficient() CO NE;IN CO uint& SZ() CO NE;IN void swap(PO<T>& f);IN void swap(VE<T>& f);void RemoveRedundantZero();IN string Display() CO NE;ST IN CO PO<T>& 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 <TY T>bool OP==(CO PO<T>& f0,CO T& t1);TE <TY T>bool OP==(CO PO<T>& f0,CO PO<T>& f1);TE <TY T,TY P> IN bool OP!=(CO PO<T>& f0,CO P& f1);TE <TY T,TY P> IN PO<T> OP+(CO PO<T>& f0,CO P& f1);TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f);TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f0,CO P& f1);TE <TY T,TY P> IN PO<T> OP*(CO PO<T>& f0,CO P& f1);TE <TY T,TY P> IN PO<T> OP/(CO PO<T>& f0,CO P& f1);TE <TY T,TY P> IN PO<T> OP%(CO PO<T>& f0,CO P& f1);TE <TY T> IN PO<T> OP<<(CO PO<T>& f,CO T& t);TE <TY T> IN T& Prod(LI<T>& f);TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_output_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_output_start);TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_output_start_plus_one);TE <TY T> TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_output_start);TE <TY T>class TRPO :PU PO<T>{friend TRPO<T> TRDifferential<T>(CO TRPO<T>& f,CO uint& N_output_start_plus_one);friend TRPO<T> TRIntegral<T>(CO TRPO<T>& f,CO uint& N_output_start);PR:uint m_N;PU:IN TRPO(CO uint& N = 0);IN TRPO(CO TRPO<T>& f);IN TRPO(CO uint& N,CO T& t);TRPO(CO uint& N,CO PO<T>& f);IN TRPO(CO uint& N,PO<T>&& f);IN TRPO(CO uint& N,CO uint& i,CO T& t);IN TRPO(CO uint& N,VE<T>&& f);IN TRPO<T>& OP=(CO TRPO<T>& f);IN TRPO<T>& OP=(CO T& t);IN TRPO<T>& OP=(CO PO<T>& f);IN TRPO<T>& OP+=(CO T& t);IN TRPO<T>& OP+=(CO PO<T>& f);IN TRPO<T>& OP+=(CO TRPO<T>& f);TRPO<T>& TRPlus(CO PO<T>& f,CO uint& N_input_start,CO uint& N_input_limit);IN TRPO<T>& OP-=(CO T& t);IN TRPO<T>& OP-=(CO PO<T>& f);IN TRPO<T>& OP-=(CO TRPO<T>& f);TRPO<T>& TRMinus(CO PO<T>& f,CO uint& N_input_start,CO uint& N_input_limit);IN TRPO<T>& OP*=(CO T& t);TRPO<T>& OP*=(CO PO<T>& f);TRPO<T>& FFT_MU(CO PO<T>& f);TRPO<T>& TRMU(CO PO<T>& f,CO uint& N_input_start,CO uint& N_input_lim);TRPO<T>& FFT_TRMU(CO PO<T>& f,CO uint& N_input_start,CO uint& N_input_lim);TRPO<T> TRMU_CO(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim) CO;TRPO<T> FFT_TRMU_CO(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim) CO;IN TRPO<T>& OP/=(CO T& t);IN TRPO<T>& OP/=(CO TRPO<T>& t);IN TRPO<T>& OP%=(CO T& t);IN TRPO<T> OP-() CO;IN void SetTruncation(CO uint& N) NE;IN CO uint& GetTruncation() CO NE;IN TRPO<T>& TruncateInitial(CO uint& N) NE;IN TRPO<T>& TruncateFinal(CO uint& N) NE;};TE <TY T> IN CE CO uint FFT_MU_border_0;TE <TY T> IN CE CO uint FFT_MU_border_1;TE <TY T> IN CE CO uint FFT_MU_border_1_2;TE <TY T> IN CE CO uint FFT_MU_border_1_2_exponent;TE <TY T> IN CE CO uint FFT_MU_border_1_2_inv;TE <TY T,TY P> IN TRPO<T> OP+(CO TRPO<T>& f0,CO P& f1);TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f);TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f0,CO P& f1);TE <TY T,TY P> IN TRPO<T> OP*(CO TRPO<T>& f0,CO P& f1);TE <TY T,TY P> IN TRPO<T> OP/(CO TRPO<T>& f0,CO P& f1);TE <TY T> IN TRPO<T> OP%(CO TRPO<T>& f0,CO T& t1);TE <TY T> IN TRPO<T> Differential(CO TRPO<T>& f);TE <TY T> IN TRPO<T> Differential(CO uint& i,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_output_start_plus_one);TE <TY T> IN TRPO<T> Integral(CO TRPO<T>& f);TE <TY T>TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_output_start);TE <TY T>TRPO<T> Inverse(CO TRPO<T>& f);TE <TY T>TRPO<T> Exp(CO TRPO<T>& f);TE <TY T> IN TRPO<T> Log(CO TRPO<T>& f);TE <TY T>TRPO<T> Power(CO TRPO<T>& f,CO T& t);TE <TY T> IN CE CO uint LimitOfPowerForFFT;TE <TY T> IN CE CO uint BorderForFFT;TE <TY T> IN CO T (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<T>];TE <TY T> IN CO T (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<T>];TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO uint& exponent);TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO uint& exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE <TY T> VE<T> IFFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent);TE <> IN CE CO uint LimitOfPowerForFFT<Mod<998244353> > = 24;TE <> IN CE CO uint BorderForFFT<Mod<998244353> > = 4; TE <> IN CO Mod<998244353> (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPowerForFFT<Mod<998244353> >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={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<Mod<998244353> >]{ST CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={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 <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT<T>]);TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power,exponent,0,1,PrimitiveRootOfTwoForFFT<T>()); }TE <TY T> IN VE<T> FFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO uint& exponent) { RE FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,N_output_start,N_output_lim,N_output_shift,two_power,exponent,PrimitiveRootOfTwoForFFT<T>()); }TE <TY T>VE<T> IFFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE<T> AN{ move(FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT<T>())) };CO uint SZ = AN.SZ();for(uint i = 0;i < SZ;i++){AN[i] *= two_power_inv;}RE AN;}TE <TY T>VE<T> IFFT(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO T& two_power_inv,CO uint& exponent){VE<T> AN{ move(FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,N_output_start,N_output_lim,N_output_shift,two_power,exponent,InversePrimitiveRootOfTwoForFFT<T>())) };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 <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& N_output_start,CO uint& N_output_lim,CO uint& N_output_shift,CO uint& two_power,CO uint& exponent,CO T (&PRT)[LimitOfPowerForFFT<T>]){CO uint length = N_output_lim - N_output_start + N_output_shift;VE<T> 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<T> AN_sub0{ move(FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,0,2,PRT)) };VE<T> AN_sub1{ move(FFT_Body<T>(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 <TY T>ST VE<T> FFT_Body(CO VE<T>& f,CO uint& N_input_start,CO uint& N_input_lim,CO uint& N_input_shift,CO uint& two_power,CO uint& exponent,CO uint& start,CO uint& depth,CO T (&PRT)[LimitOfPowerForFFT<T>]){VE<T> 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 CO uint& border = BorderForFFT<T>;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<T> AN_sub0{ move(FFT_Body<T>(f,N_input_start,N_input_lim,N_input_shift,two_power_sub,exponent_sub,start,depth_sub,PRT)) };VE<T> AN_sub1{ move(FFT_Body<T>(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 <TY T> IN TRPO<T>::TRPO(CO uint& N):PO<T>(),m_N(N) {}TE <TY T> IN TRPO<T>::TRPO(CO TRPO<T>& f):PO<T>(f),m_N(f.m_N) {}TE <TY T> IN TRPO<T>::TRPO(CO uint& N,CO T& t):PO<T>(t),m_N(N) {}TE <TY T>TRPO<T>::TRPO(CO uint& N,CO PO<T>& f):PO<T>(),m_N(N){CO uint& SZ = f.PO<T>::m_SZ < m_N ? f.PO<T>::m_SZ:m_N;for(uint i = 0;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);PO<T>::m_SZ++;}}TE <TY T> IN TRPO<T>::TRPO(CO uint& N,PO<T>&& f):PO<T>(move(f)),m_N(N) {};TE <TY T> IN TRPO<T>::TRPO(CO uint& N,CO uint& i,CO T& t):PO<T>(),m_N(N) { if(i < m_N ? t != PO<T>::CO_zero():false){ PO<T>::OP[](i) = t; } }TE <TY T> IN TRPO<T>::TRPO(CO uint& N,VE<T>&& f):PO<T>(move(f)),m_N(N){WH(PO<T>::m_SZ > m_N){PO<T>::m_f.pop_back();PO<T>::m_SZ--;}}TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO TRPO<T>& f) { PO<T>::OP=(f); m_N = f.m_N; RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO T& t) { PO<T>::OP=(t); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO PO<T>& f) { RE OP=(TRPO<T>(m_N,f)); }TE <TY T> IN TRPO<T>& TRPO<T>::OP+=(CO T& t) { PO<T>::OP+=(t); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP+=(CO PO<T>& f) { RE TRPO<T>::TRPlus(f,0,f.PO<T>::m_SZ); }TE <TY T> IN TRPO<T>& TRPO<T>::OP+=(CO TRPO<T>& f) { RE m_N == 0 ? OP=(f):TRPO<T>::TRPlus(f,0,f.PO<T>::m_SZ); }TE <TY T>TRPO<T>& TRPO<T>::TRPlus(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_limit){CO uint& SZ = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_SZ ? N_output_limit:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;CO uint& SZ_min = PO<T>::m_SZ < SZ ? PO<T>::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}for(uint i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);PO<T>::m_SZ++;}RE *this;}TE <TY T> IN TRPO<T>& TRPO<T>::OP-=(CO T& t) { PO<T>::OP-=(t); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP-=(CO PO<T>& f) { RE TRPO<T>::TRMinus(f,0,f.PO<T>::m_SZ); }TE <TY T> IN TRPO<T>& TRPO<T>::OP-=(CO TRPO<T>& f) { RE m_N == 0 ? OP=(-f):TRPO<T>::TRMinus(f,0,f.PO<T>::m_SZ); }TE <TY T>TRPO<T>& TRPO<T>::TRMinus(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_limit){CO uint& SZ = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_SZ ? N_output_limit:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ ? m_N:f.PO<T>::m_SZ;CO uint& SZ_min = PO<T>::m_SZ < SZ ? PO<T>::m_SZ:SZ;for(uint i = N_output_start;i < SZ_min;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}for(uint i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(- f.PO<T>::m_f[i]);PO<T>::m_SZ++;}RE *this;}TE <TY T> IN TRPO<T>& TRPO<T>::OP*=(CO T& t) { PO<T>::OP*=(t); RE *this; }DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_POLYNOMIAL(Mod<998244353>,12,512,1024,10,997269505); TE <TY T>TRPO<T>& TRPO<T>::OP*=(CO PO<T>& f){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO<T>::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 <TY T>TRPO<T>& TRPO<T>::FFT_MU(CO PO<T>& f){CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){RE_ZERO_FOR_MU_FOR_TR_POLYNOMIAL_IF(f.PO<T>::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 CO uint& border_1 = FFT_MU_border_1<T>;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<T>::m_f = move(IFFT<T>(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<T>::m_SZ = PO<T>::m_f.SZ();}}RE *this;}TE <TY T> TRPO<T>& TRPO<T>::TRMU(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::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 <TY T> TRPO<T>& TRPO<T>::FFT_TRMU(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim){CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::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 CO uint& border_1 = FFT_MU_border_1<T>;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 = move(IFFT<T>(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<T>::m_f[i] = f0[i];}}}RE *this;}TE <TY T> TRPO<T> TRPO<T>::TRMU_CO(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim) CO{CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,move(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<T>(m_N,move(AN));}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMU_CO(CO PO<T>& f,CO uint& N_output_start,CO uint& N_output_lim) CO{CE CO uint& border_0 = FFT_MU_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if(PO<T>::m_SZ < border_0 && f.PO<T>::m_SZ < border_0){DF_0_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,move(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 CO uint& border_1 = FFT_MU_border_1<T>;if(N_input_truncated_deg_0_deg_1 < border_1){DF_3_OF_TR_MU_CO_FOR_TR_POLYNOMIAL;RE TRPO<T>(m_N,move(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<T>(m_N,move(IFFT<T>(f0,0,two_power,0,N_output_start_shifted,N_output_lim_shifted,N_output_shift_shifted,two_power,two_power_inv,exponent)));}TE <TY T> IN TRPO<T>& TRPO<T>::OP/=(CO T& t) { PO<T>::OP/=(t); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP/=(CO TRPO<T>& f) { RE OP*=(Inverse(m_N > f.m_N ? f:TRPO<T>(m_N,f))); }TE <TY T> IN TRPO<T>& TRPO<T>::OP%=(CO T& t) { PO<T>::OP%=(t); RE *this; }TE <TY T> IN TRPO<T> TRPO<T>::OP-() CO { RE TRPO<T>(m_N).OP-=(*this); }TE <TY T> IN void TRPO<T>::SetTruncation(CO uint& N) NE { m_N = N; TruncateFinal(m_N); }TE <TY T> IN CO uint& TRPO<T>::GetTruncation() CO NE { RE m_N; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateInitial(CO uint& N) NE { CO uint& SZ = N < PO<T>::m_SZ ? N:PO<T>::m_SZ; for(uint i = 0;i < SZ;i++){ PO<T>::m_f[i] = 0; } RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateFinal(CO uint& N) NE { WH(PO<T>::m_SZ > N){ PO<T>::m_f.pop_back(); PO<T>::m_SZ--; } RE *this; }TE <TY T,TY P> IN TRPO<T> OP+(CO TRPO<T>& f0,CO P& f1) { RE TRPO<T>(f0).OP+=(f1); }TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f) { RE TRPO<T>(f).OP*=(PO<T>::CO_minus_one()); }TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f0,CO P& f1) { RE TRPO<T>(f0).OP-=(f1); }TE <TY T,TY P> IN TRPO<T> OP*(CO TRPO<T>& f0,CO P& f1) { RE TRPO<T>(f0).OP*=(f1); }TE <TY T,TY P> IN TRPO<T> OP/(CO TRPO<T>& f0,CO P& f1) { RE TRPO<T>(f0).OP*=(Inverse(f1)); }TE <TY T> IN TRPO<T> OP%(CO TRPO<T>& f0,CO T& t1) { RE TRPO<T>(f0).OP%=(t1); }TE <TY T> IN TRPO<T> Differential(CO TRPO<T>& f) { RE TRDifferential<T>(f,1); }TE <TY T> IN TRPO<T> Differential(CO uint& i,CO TRPO<T>& f) { RE i == 0 ? f:Differential<T>(i - 1,Differential<T>(f)); }TE <TY T>TRPO<T> TRDifferential(CO TRPO<T>& f,CO uint& N_output_start_plus_one){if(f.m_N == 0){RE TRPO<T>();}TRPO<T> f_dif{ f.m_N - 1 };if(N_output_start_plus_one < f.PO<T>::m_SZ){for(uint i = 1;i < N_output_start_plus_one;i++){f_dif.PO<T>::m_f.push_back(0);}for(uint i = N_output_start_plus_one;i < f.PO<T>::m_SZ;i++){f_dif.PO<T>::m_f.push_back(i * f.PO<T>::m_f[i]);}f_dif.PO<T>::m_SZ = f.PO<T>::m_SZ - 1;}RE f_dif;}TE <TY T> IN TRPO<T> Integral(CO TRPO<T>& f) { RE TRIntegral<T>(f,1); }TE <TY T>TRPO<T> TRIntegral(CO TRPO<T>& f,CO uint& N_output_start){TRPO<T> f_int{ f.m_N + 1 };if(N_output_start <= f.PO<T>::m_SZ){for(uint i = 0;i < N_output_start;i++){f_int.PO<T>::m_f.push_back(0);}for(uint i = N_output_start;i <= f.PO<T>::m_SZ;i++){f_int.PO<T>::m_f.push_back(f.PO<T>::m_f[i - 1] / T(i));}f_int.PO<T>::m_SZ = f.PO<T>::m_SZ + 1;}RE f_int;}TE <TY T>TRPO<T> Inverse(CO TRPO<T>& 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 <TY T>TRPO<T> Exp(CO TRPO<T>& 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 <TY T> IN TRPO<T> Log(CO TRPO<T>& f) { RE Integral<T>(Differential<T>(f) /= f); }TE <TY T> IN TRPO<T> Power(CO TRPO<T>& f,CO T& t) { RE Exp(Log(f) *= t); }TE <TY T> IN PO<T>::PO():m_f(),m_SZ(0) {}TE <TY T> IN PO<T>::PO(CO T& t):PO() { if(t != CO_zero()){ OP[](0) = t; } }TE <TY T> IN PO<T>::PO(CO PO<T>& f):m_f(f.m_f),m_SZ(f.m_SZ) {}TE <TY T> IN PO<T>::PO(PO<T>&& f):m_f(move(f.m_f)),m_SZ(move(f.m_SZ)) {}TE <TY T> IN PO<T>::PO(CO uint& i,CO T& t):PO() { if(t != CO_zero()){ OP[](i) = t; } }TE <TY T> IN PO<T>::PO(VE<T>&& f):m_f(move(f)),m_SZ(m_f.SZ()) {}TE <TY T> IN PO<T>& PO<T>::OP=(CO T& t) { m_f.clear(); m_SZ = 0; OP[](0) = t; RE *this; }TE <TY T> IN PO<T>& PO<T>::OP=(CO PO<T>& f) { m_f = f.m_f; m_SZ = f.m_SZ; RE *this; }TE <TY T>CO T& PO<T>::OP[](CO uint& i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::OP[](CO 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 <TY T> IN T PO<T>::OP()(CO T& t) CO { RE (*this % (PO<T>(1,CO_one()) - t))[0]; }TE <TY T> IN PO<T>& PO<T>::OP+=(CO T& t) { OP[](0) += t; RE *this; }TE <TY T>PO<T>& PO<T>::OP+=(CO PO<T>& f){for(uint i = 0;i < f.m_SZ;i++){OP[](i) += f.m_f[i];}RE *this;}TE <TY T> IN PO<T>& PO<T>::OP-=(CO T& t) { OP[](0) -= t; RE *this; }TE <TY T>PO<T>& PO<T>::OP-=(CO PO<T>& 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 <TY T>PO<T>& PO<T>::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 <TY T>PO<T>& PO<T>::OP*=(CO PO<T>& 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<T> 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=(move(product));}TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == CO_one()){RE *this;}for(uint i = 0;i < m_SZ;i++){OP[](i) /= t;}RE *this;}TE <TY T>PO<T>& PO<T>::OP/=(CO PO<T>& f){if(m_SZ >= f.m_SZ){assert(f.m_SZ > 0);uint SZ0 = m_SZ - f.m_SZ + 1;TRPO<T> f0_copy(SZ0);for(uint d0 = 0;d0 < SZ0;d0++){f0_copy.PO<T>::m_f.push_back(m_f[m_SZ - 1 - d0]);}f0_copy.PO<T>::m_SZ = SZ0;TRPO<T> f1_copy(SZ0);uint SZ1 = SZ0 < f.m_SZ ? SZ0:f.m_SZ;for(uint d1 = 0;d1 < SZ1;d1++){f1_copy.PO<T>::m_f.push_back(f.m_f[f.m_SZ - 1 - d1]);}f1_copy.PO<T>::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<T>::m_f.clear();PO<T>::m_SZ = 0;}RE *this;}TE <TY T>PO<T>& PO<T>::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 <TY T>PO<T>& PO<T>::OP%=(CO PO<T>& f){if(m_SZ >= f.m_SZ){OP-=((*this / f) * f);RemoveRedundantZero();}RE *this;}TE <TY T> IN PO<T> PO<T>::OP-() CO { RE PO<T>().OP-=(*this); }TE <TY T >PO<T>& PO<T>::OP<<=(CO T& t){if(m_SZ > 0){ST T factorial_curr = 1;ST VE<T> factorial = { 1,1 };ST T factorial_inv_curr = 1;ST VE<T> 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<T> 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<T>::m_f[d + m_SZ - 1] * factorial_inv[d];}}RE *this;}TE <TY T> IN CO VE<T>& PO<T>::GetCoefficient() CO NE { RE m_f; }TE <TY T> IN CO uint& PO<T>::SZ() CO NE { RE m_SZ; }TE <TY T> IN void PO<T>::swap(PO<T>& f) { m_f.swap(f.m_f); swap(m_SZ,f.m_SZ); }TE <TY T> IN void PO<T>::swap(VE<T>& f) { m_f.swap(f); m_SZ = m_f.SZ(); }TE <TY T>void PO<T>::RemoveRedundantZero(){CO T& z = CO_zero();WH(m_SZ > 0 ? m_f[m_SZ - 1] == z:false){m_f.pop_back();m_SZ--;}RE;}TE <TY T>string PO<T>::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 <TY T> IN CO PO<T>& PO<T>::zero() { ST CO PO<T> z{}; RE z; }TE <TY T> IN CO T& PO<T>::CO_zero() { ST CO T z{ 0 }; RE z; }TE <TY T> IN CO T& PO<T>::CO_one() { ST CO T o{ 1 }; RE o; }TE <TY T> IN CO T& PO<T>::CO_minus_one() { ST CO T m{ -1 }; RE m; }TE <TY T> IN CO T& PO<T>::factorial(CO uint& i) { ST VE<T> 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 <TY T> IN CO T& PO<T>::factorial_inverse(CO uint& i) { ST VE<T> 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 <TY T>bool OP==(CO PO<T>& f0,CO T& t1){CO uint& SZ = f0.SZ();CO T& zero = PO<T>::CO_zero();for(uint i = 1;i < SZ;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE <TY T>bool OP==(CO PO<T>& f0,CO PO<T>& f1){CO uint& SZ0 = f0.SZ();CO uint& SZ1 = f1.SZ();CO uint& SZ = SZ0 < SZ1 ? SZ1:SZ0;for(uint i = 0;i < SZ;i++){if(f0[i] != f1[i]){RE false;}}RE true;}TE <TY T,TY P> IN bool operator!=(CO PO<T>& f0,CO P& f1) { RE !(f0 == f1); }TE <TY T,TY P> IN PO<T> operator+(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; f += f1; RE f; }TE <TY T,TY P> IN PO<T> operator-(CO PO<T>& f) { RE PO<T>::zero() - f; }TE <TY T,TY P> IN PO<T> operator-(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator-=(f1); }TE <TY T,TY P> IN PO<T> operator*(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator*=(f1); }TE <TY T,TY P> IN PO<T> operator/(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator/=(f1); }TE <TY T,TY P> IN PO<T> operator%(CO PO<T>& f0,CO P& f1) { PO<T> f = f0; RE f.operator%=(f1); }TE <TY T> PO<T> operator<<(CO PO<T>& f,CO T& t) { RE PO<T>(f) <<= t; };TE <TY T> IN T& Prod(LI<T>& 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 <TY T,TY V> IN void SetMultipointEvaluation(CO PO<T>& f,CO V& point,V& AN);TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& AN);TE <TY T> IN void SetMultipointEvaluation(CO PO<T>& f,CO LI<T>& point,LI<T>& AN);TE <TY T>void SetProductTree(LI<LI<T> >& product_tree);TE <TY T,TY V>void SetPointTree(CO V& point,LI<LI<PO<T> > >& point_tree);TE <TY T,TY V> IN void SetMultipointEvaluation(CO PO<T>& f,CO V& point,V& AN) { LI<LI<PO<T> > > pt{}; SetPointTree(point,pt); SetMultipointEvaluation(f,pt,AN); }TE <TY T,TY V>void SetMultipointEvaluation(CO PO<T>& f,CO LI<LI<PO<T> > >& point_tree,V& AN){CO LI<PO<T> >& prod = point_tree.front();if(prod.empty()){RE;}LI<PO<T> > residue = {};CO PO<T>& zero = PO<T>::zero();residue.push_back(zero);residue.back() = move(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<T>& 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++){AN.push_back((*I_residue)[0]);}RE;}TE <TY T>void SetProductTree(LI<LI<T> >& product_tree){LI<T> empty{};LI<T> *p_node = &(product_tree.back());WH(p_node->SZ() > 1){product_tree.push_front(empty);LI<T>& 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 <TY T,TY V>void SetPointTree(CO V& point,LI<LI<PO<T> > >& point_tree){ST CO LI<PO<T> > empty{};point_tree.push_front(empty);LI<PO<T> >& linear = point_tree.front();for(auto I = point.begin(),end = point.end();I != end;I++){ST CO PO<T> x{ 1,PO<T>::CO_one() };linear.push_back(x);linear.back()[0] -= *I;}SetProductTree(point_tree);RE;}TE <TY T>using TT = VE<VE<T> >;TE <uint Y,uint X,TY T>class MA{PR:TT<T> m_M;PU:IN MA(CO T& t) NE;IN MA(CO int& t) NE;TE <TY... Args> MA(CO Args&... args) NE;IN MA(CO MA<Y,X,T>& mat) NE;IN MA(MA<Y,X,T>&& mat) NE;TE <TY... Args> IN MA(CO TT<T>& M) NE;TE <TY... Args> IN MA(TT<T>&& M) NE;IN MA<Y,X,T>& operator=(CO MA<Y,X,T>& mat) NE;MA<Y,X,T>& operator+=(CO MA<Y,X,T>& mat);MA<Y,X,T>& operator-=(CO MA<Y,X,T>& mat);MA<Y,X,T>& operator*=(CO T& scalar) NE;IN MA<Y,X,T>& operator*=(CO MA<X,X,T>& mat) NE;MA<Y,X,T>& operator%=(CO T& scalar) NE;IN TT<T>& RefTable() NE;IN CO TT<T>& GetTable() CO NE;ST IN CO MA<Y,X,T>& Zero() NE;ST IN CO MA<Y,X,T>& Unit() NE;ST MA<Y,X,T> Scalar(CO T& t) NE;PR:ST IN void COructTable(TT<T>& M,VE<T>& vec) NE;TE <TY... Args> ST void COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE;ST MA<Y,X,T> Zero_Body() NE;};TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <uint Y,uint X,uint Z,TY T>MA<Y,Z,T> operator*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO MA<Y,X,T>& mat,CO T& scalar);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat);TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator%(CO MA<Y,X,T>& mat,CO T& scalar);TE <uint Y,uint X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat);TE <uint X,TY T>T Trace(CO MA<X,X,T>& mat);TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO T& t) NE:m_M() { operator=(move(Scalar(t))); }TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO int& t) NE:MA(T(1)) {}TE <uint Y,uint X,TY T> TE <TY... Args>MA<Y,X,T>::MA(CO Args&... args) NE: m_M(){VE<T> vec{};COructTable(m_M,vec,args...);}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(CO MA<Y,X,T>& mat) NE:m_M(mat.m_M) {}TE <uint Y,uint X,TY T> IN MA<Y,X,T>::MA(MA<Y,X,T>&& mat) NE:m_M(move(mat.m_M)) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO TT<T>& M) NE:m_M(M) {}TE <uint Y,uint X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(TT<T>&& M) NE:m_M(move(M)) {}TE <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator=(CO MA<Y,X,T>& mat) NE { m_M = mat.m_M; RE *this; }TE <uint Y,uint X,TY T>MA<Y,X,T>& MA<Y,X,T>::operator+=(CO MA<Y,X,T>& 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 <uint Y,uint X,TY T>MA<Y,X,T>& MA<Y,X,T>::operator-=(CO MA<Y,X,T>& 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 <uint Y,uint X,TY T> MA<Y,X,T>& MA<Y,X,T>::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 <uint Y,uint X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::operator*=(CO MA<X,X,T>& mat) NE { RE operator=(move(*this * mat)); }TE <uint Y,uint X,TY T> MA<Y,X,T>& MA<Y,X,T>::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 <uint Y,uint X,TY T> IN TT<T>& MA<Y,X,T>::RefTable() NE { RE m_M; }TE <uint Y,uint X,TY T> IN CO TT<T>& MA<Y,X,T>::GetTable() CO NE { RE m_M; }TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Zero() NE { ST CO MA<Y,X,T> zero = move(Zero_Body()); RE zero; }TE <uint Y,uint X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Unit() NE { ST CO MA<Y,X,T> unit = move(Scalar(T(1))); RE unit; }TE <uint Y,uint X,TY T>MA<Y,X,T> MA<Y,X,T>::Zero_Body() NE{VE<T> vec(X);TT<T> M(Y,vec);RE MA<Y,X,T>(move(M));}TE <uint Y,uint X,TY T>MA<Y,X,T> MA<Y,X,T>::Scalar(CO T& t) NE{MA<Y,X,T> 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 <uint Y,uint X,TY T> IN void MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec) NE { M.push_back(move(vec)); }TE <uint Y,uint X,TY T> TE <TY... Args> void MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE{vec.push_back(t);if(vec.SZ() == X){VE<T> v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,args...);}RE;}TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE { RE mat1.GetTable() == mat2.GetTable(); }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE { RE !(mat1 == mat2); }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) { RE MA<Y,X,T>(mat1) += mat2; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) { RE MA<Y,X,T>(mat1) -= mat2; }TE <uint Y,uint X,uint Z,TY T> IN MA<Y,Z,T> operator*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2){CO TT<T>& M1 = mat1.GetTable();CO TT<T>& M2 = mat2.GetTable();TT<T> M_prod{};auto begin2x = M2.begin();for(auto I1y = M1.begin(),end1y = M1.end();I1y != end1y;I1y++){VE<T> 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(move(vec));}RE MA<Y,Z,T>(move(M_prod));}TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO MA<Y,X,T>& mat,CO T& scalar) { RE MA<Y,X,T>(mat) *= scalar; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator*(CO T& scalar,CO MA<Y,X,T>& mat) { RE mat * scalar; }TE <uint Y,uint X,TY T> IN MA<Y,X,T> operator%(CO MA<Y,X,T>& mat,CO T& scalar) { RE MA<Y,X,T>(mat) %= scalar; }TE <uint Y,uint X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat){CO TT<T>& M = mat.GetTable();TT<T> M_t{};auto beginy = M.begin();for(auto I1x = beginy->begin(),end1x = beginy->end();I1x != end1x;I1x++){M_t.push_back(VE<T>());}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<X,Y,T>(M_t);}TE <uint X,TY T>T Trace(CO MA<X,X,T>& mat){int i = 0;T AN =0;CO TT<T>& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){AN += (*Iy)[i];i++;}RE AN;}TE <TY T>void SetIntervalEvaluation(CO uint& deg,CO T& t_start,CO uint& length,VE<T>& eval){for(uint d = 0;d <= deg;d++){eval[d] *= PO<T>::factorial_inverse(d);}VE<T> v{};v.swap(eval);TRPO<T> f{ deg + 1,move(v) };ST PO<T> exp_inv{};for(uint d = exp_inv.SZ();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO<T>::factorial_inverse(d):- PO<T>::factorial_inverse(d));}f *= exp_inv;f.RemoveRedundantZero();uint deg_f = f.SZ();if(deg_f == 0){eval = move(VE<T>(length,PO<T>::CO_zero()));RE;}f.SetTruncation(deg_f);deg_f--;for(uint d = 0;d <= deg_f;d++){f[d] *= PO<T>::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<T> exp_t_Mahler{};T t_Mahler = PO<T>::CO_one();for(uint d = 0;d <= deg_f;d++){exp_t_Mahler[d] = PO<T>::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<T>::factorial_inverse(d);}f.SetTruncation(length);ST PO<T> exp{};for(uint d = exp.SZ();d < length;d++){exp[d] = PO<T>::factorial_inverse(d);}f *= exp;for(uint d = 0;d < length;d++){f[d] *= PO<T>::factorial(d);}f.swap(eval);RE;}TE <uint Y,uint X,TY T>void SetIntervalEvaluation(CO uint& deg,CO T& t_start,CO uint& length,CO VE<MA<Y,X,T> >& sample,VE<MA<Y,X,T> >& eval){eval = move(VE<MA<Y,X,T> >(length,MA<Y,X,T>::Zero()));VE<T> sample_copy[Y][X] = {};for(uint t = 0;t <= deg;t++){CO VE<VE<T> >& table = sample[t].GetTable();for(uint y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];CO VE<T>& 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<T> (&sample_copy_y)[X] = sample_copy[y];for(uint x = 0;x < X;x++){VE<T>& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,length,sample_copy_yx);for(uint i = 0;i < length;i++){VE<VE<T> >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}}RE;}TE <uint Y,TY T>void SetPRecursiveMAAction(CO MA<Y,Y,PO<T> >& M,MA<Y,1,T>& v,CO uint& length){if(length == 0){RE;}CO VE<VE<PO<T> > >& M_ref = M.GetTable();uint deg = 1;for(uint y = 0;y < Y;y++){CO VE<PO<T>>& 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<T> 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<T>::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 = 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_MA_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; }using MOD = Mod<P>;using MODX = PO<MOD>;class D{PU:MA<2,2,MODX> m_M;MODX m_pt;IN D() = default;IN D(MA<2,2,MODX>&& M,MODX&& pt):m_M(move(M)),m_pt(move(pt)) {}IN D(CO D& d):m_M(d.m_M),m_pt(d.m_pt) {}IN D(D&& d):m_M(move(d.m_M)),m_pt(move(d.m_pt)) {}IN D& operator=(CO D& d) { m_M = d.m_M; m_pt = d.m_pt; RE *this; }IN D& operator=(D&& d) { m_M = move(d.m_M); m_pt = move(d.m_pt); RE *this; }IN D& operator*=(CO D& d) { m_M *= d.m_M; m_pt *= d.m_pt; RE *this; }};IN D operator*(CO D& d1,CO D& d2) { RE D(move(d1.m_M * d2.m_M),move(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(true){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);LI<LI<D> > d_prod{};d_prod.push_front(LI<D>());LI<D>& d_prod_init = d_prod.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(move(D(move(MA<2,2,MODX>{X * CO_two - CO_two * k,X * k + CO_two_inv * ((1 - k) * k),one,zero}),move(MODX(one)))));}d_prod_init.push_front(move(D(move(MA<2,2,MODX>(1)),move(X - Qt.m_N))));k_start = Qt.m_K;}SetProductTree(d_prod);LI<MA<2,2,MODX> > residue{};residue.push_front(move(MA<2,2,MODX>(1)));auto I_d_prod = d_prod.begin(),end_d_prod = d_prod.end();I_d_prod++;WH(I_d_prod != end_d_prod){auto I_d_prod_node = I_d_prod->begin(),end_d_prod_node = I_d_prod->end();FOR_I(residue,I_residue,end_residue){MODX& pt_node_curr = I_d_prod_node->m_pt;I_d_prod_node++;if(I_d_prod_node != end_d_prod_node){residue.insert(I_residue,move(((I_d_prod_node->m_M %= pt_node_curr) * (*I_residue % pt_node_curr)) %= pt_node_curr));*I_residue %= I_d_prod_node->m_pt;I_d_prod_node++;} else {break;}}I_d_prod++;}ST ll AN[bound_T];auto I_d_prod_node = d_prod.back().begin();auto I_residue = residue.begin();FOREQINV(t,T - 1,0){WH(I_d_prod_node->m_pt.SZ() == 1){I_d_prod_node++;I_residue++;}CO VE<VE<MODX> >& residue_t = I_residue->m_M;CO VE<MODX>& residue_t_0 = residue_t[0];CO VE<MODX>& 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]};AN[Q[t].m_t] = (residue_t_val * v).m_M[0][0].Represent();I_d_prod_node++;I_residue++;}FOR(t,0,T){cout << AN[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;}
0