#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include #define TE template #define TY typename #define US using #define ST static #define IN inline #define CL class #define PU public #define PR PU #define OP operator #define CE constexpr #define CO const #define RE return #define WH while #define VO void #define VE vector #define LI list #define CRI CO int& #define CRUI CO UI& #define CRL CO ll& #define SZ size #define MO move using namespace std;using UI = unsigned int;using ll = long long; #define TYPE_OF(VAR) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio(false);cin.tie(nullptr) #define CEXPR(LL,BOUND,VALUE) constexpr const LL BOUND = VALUE #define CIN(LL,A) LL A;cin >> A #define ASSERT(A,MIN,MAX) assert(MIN <= A && A <= MAX) #define CIN_ASSERT(A,MIN,MAX) CIN(TYPE_OF(MAX),A);ASSERT(A,MIN,MAX) #define FOR(VAR,INITIAL,FINAL_PLUS_ONE) for(TYPE_OF(FINAL_PLUS_ONE) VAR = INITIAL;VAR < FINAL_PLUS_ONE;VAR ++) #define FOREQ(VAR,INITIAL,FINAL) for(TYPE_OF(FINAL) VAR = INITIAL;VAR <= FINAL;VAR ++) #define FOREQINV(VAR,INITIAL,FINAL) for(TYPE_OF(INITIAL) VAR = INITIAL;VAR >= FINAL;VAR --) #define FOR_ITR(ARRAY,ITR,END) for(auto ITR = ARRAY .begin(),END = ARRAY .end();ITR != END;ITR ++) #define REPEAT(HOW_MANY_TIMES) FOR(VARIABLE_FOR_REPEAT,0,HOW_MANY_TIMES) #define COUT(ANSWER) cout << (ANSWER) << "\n"; #define DC_OF_CM_FOR_MOD(NAME) IN bool NAME (CO Mod& n) CO;IN bool NAME (CRL n) CO;IN bool NAME (ll&& n) CO; #define DF_OF_CM_FOR_MOD(NAME,OP_SYMBOL) TE IN bool Mod:: NAME (CO Mod& n) CO {RE m_n OP_SYMBOL n.m_n;} TE IN bool Mod:: NAME (CRL n) CO {RE m_n OP_SYMBOL RS(n,M);} TE IN bool Mod:: NAME (ll&& n) CO {RE m_n OP_SYMBOL RS(MO(n),M);} #define DC_OF_OP_FOR_MOD(TYPE,OP_SYMBOL) TE IN TYPE OP OP_SYMBOL(CO Mod& n0,CO Mod& n1);TE IN TYPE OP OP_SYMBOL(CO Mod& n0,CRL n1);TE IN TYPE OP OP_SYMBOL(CO Mod& n0,ll&& n1);TE IN TYPE OP OP_SYMBOL(CRL n0,CO Mod& n1);TE IN TYPE OP OP_SYMBOL(ll&& n0,CO Mod& n1); #define DC_OF_CM_OP_FOR_MOD(OP_SYMBOL) DC_OF_OP_FOR_MOD(bool,OP_SYMBOL); #define DF_OF_CM_OP_FOR_MOD(OP_SYMBOL,NAME,NAME_INV) TE IN bool OP OP_SYMBOL(CO Mod& n0,CO Mod& n1) {RE n0. NAME (n1);} TE IN bool OP OP_SYMBOL(CO Mod& n0,CRL n1) {RE n0. NAME (n1);} TE IN bool OP OP_SYMBOL(CO Mod& n0,ll&& n1) {RE n0. NAME (MO(n1));} TE IN bool OP OP_SYMBOL(CRL n0,CO Mod& n1) {RE n1. NAME_INV (n0);} TE IN bool OP OP_SYMBOL(ll&& n0,CO Mod& n1) {RE n1. NAME_INV (MO(n0));} #define DC_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DC_OF_OP_FOR_MOD(Mod,OP_SYMBOL);TE IN Mod OP OP_SYMBOL(Mod&& n0,CO Mod& n1);TE IN Mod OP OP_SYMBOL(CO Mod& n0,Mod&& n1);TE IN Mod OP OP_SYMBOL(Mod&& n0,Mod&& n1);TE IN Mod OP OP_SYMBOL(Mod&& n0,CRL n1);TE IN Mod OP OP_SYMBOL(Mod&& n0,ll&& n1);TE IN Mod OP OP_SYMBOL(CRL n0,Mod&& n1);TE IN Mod OP OP_SYMBOL(ll&& n0,Mod&& n1); #define DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) TE IN Mod OP OP_SYMBOL(CO Mod& n0,CO Mod& n1) {RE MO(Mod(n0) OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL(Mod&& n0,CO Mod& n1) {RE MO(n0 OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL(Mod&& n0,Mod&& n1) {RE MO(n0 OP_SYMBOL ## = MO(n1));} TE IN Mod OP OP_SYMBOL(CO Mod& n0,CRL n1) {RE MO(Mod(n0) OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL(Mod&& n0,CRL n1) {RE MO(n0 OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL(CO Mod& n0,ll&& n1) {RE MO(Mod(n0) OP_SYMBOL ## = MO(n1));} TE IN Mod OP OP_SYMBOL(Mod&& n0,ll&& n1) {RE MO(n0 OP_SYMBOL ## = MO(n1));} TE IN Mod OP OP_SYMBOL (CRL n0,CO Mod& n1) {RE MO(Mod(n0) OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL (ll&& n0,CO Mod& n1) {RE MO(Mod(MO(n0)) OP_SYMBOL ## = n1);} TE IN Mod OP OP_SYMBOL (ll&& n0,Mod&& n1) {RE MO(Mod(MO(n0)) OP_SYMBOL ## = MO(n1));} #define DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL);TE IN Mod OP OP_SYMBOL(CO Mod& n0,Mod&& n1) {RE MO(Mod(n0) OP_SYMBOL ## = MO(n1));} TE IN Mod OP OP_SYMBOL (CRL n0,Mod&& n1) {RE MO(Mod(n0) OP_SYMBOL ## = MO(n1));} #define DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL) DF_OF_ARITHMETIC_OP_FOR_MOD(OP_SYMBOL);TE IN Mod OP OP_SYMBOL(CO Mod& n0,Mod&& n1) {RE MO(n1 OP_SYMBOL ## = n0);} TE IN Mod OP OP_SYMBOL (CRL n0,Mod&& n1) {RE MO(n1 OP_SYMBOL ## = n0);} TE CL Mod{PR:ll m_n;ST CE CO ll g_memory_bound = 1000000;ST CE CO ll g_memory_LE = M < g_memory_bound ? M:g_memory_bound;PU:IN Mod();IN Mod(CO Mod& n);IN Mod(Mod&& n);IN Mod(CRL n);IN Mod(ll&& n);IN Mod& OP=(CO Mod& n);IN Mod& OP=(Mod&& n);IN Mod& OP=(CRL n);IN Mod& OP=(ll&& n);IN Mod& OP+=(CO Mod& n);IN Mod& OP+=(CRL n);IN Mod& OP-=(CO Mod& n);IN Mod& OP-=(CRL n);IN Mod& OP*=(CO Mod& n);IN Mod& OP*=(CRL n);IN Mod& OP*=(ll&& n);IN Mod& OP/=(CO Mod& n);IN Mod& OP/=(Mod&& n);IN Mod& OP/=(CRL n);IN Mod& OP/=(ll&& n);IN Mod& OP%=(CO Mod& n);IN Mod& OP%=(CRL n);IN Mod& OP%=(ll&& n);IN Mod OP-() CO;IN Mod& OP++();IN Mod& OP++(int);IN Mod& OP--();IN Mod& OP--(int);IN CRL Represent() CO;IN Mod& Invert();DC_OF_CM_FOR_MOD(IsEqualTo);DC_OF_CM_FOR_MOD(IsNotEqualTo);DC_OF_CM_FOR_MOD(IsSmallerThan);DC_OF_CM_FOR_MOD(IsSmallerThanOrEqualTo);DC_OF_CM_FOR_MOD(IsBiggerThan);DC_OF_CM_FOR_MOD(IsBiggerThanOrEqualTo);IN VO swap(Mod& n);ST IN CO Mod& Inverse(CRL n);ST IN CO Mod& Factorial(CRL n);ST IN CO Mod& FactorialInverse(CRL n);ST IN CO Mod& zero();ST IN CO Mod& one();PR:ST IN Mod error();};DC_OF_CM_OP_FOR_MOD(==);DC_OF_CM_OP_FOR_MOD(!=);DC_OF_CM_OP_FOR_MOD(<);DC_OF_CM_OP_FOR_MOD(<=);DC_OF_CM_OP_FOR_MOD(>);DC_OF_CM_OP_FOR_MOD(>=);DC_OF_ARITHMETIC_OP_FOR_MOD(+);DC_OF_ARITHMETIC_OP_FOR_MOD(-);DC_OF_ARITHMETIC_OP_FOR_MOD(*);DC_OF_ARITHMETIC_OP_FOR_MOD(/);DC_OF_ARITHMETIC_OP_FOR_MOD(%);TE Mod IN Inverse(CO Mod& n);TE Mod PW(CO Mod& n,CRL p);TE <> IN Mod<2> PW(CO Mod<2>& n,CRL p);TE IN Mod PW(CO Mod& n,CO Mod& p);TE <> IN Mod<2> PW(CO Mod<2>& n,CO Mod<2>& p);TE IN T Square(CO T& t);TE <> IN Mod<2> Square >(CO Mod<2>& t);TE IN VO swap(Mod& n0,Mod& n1);TE IN string to_string(CO Mod& n);TE IN basic_ostream& OP<<(basic_ostream& os,CO Mod& n);TE IN INT RS(CO INT& n,CO INT& M) {RE n >= 0 ? n % M:M - 1 - (- (n + 1));}TE IN INT RS(INT&& n,CO INT& M) {RE MO(n >= 0 ? n %= M:((((++n) *= -1) %= M) *= -1) += M - 1);}TE IN Mod::Mod():m_n() {}TE IN Mod::Mod(CO Mod& n):m_n(n.m_n) {}TE IN Mod::Mod(Mod&& n):m_n(MO(n.m_n)) {}TE IN Mod::Mod(CRL n):m_n(RS(n,M)) {}TE IN Mod::Mod(ll&& n):m_n(RS(MO(n),M)) {}TE IN Mod& Mod::OP=(CO Mod& n) {m_n = n.m_n;RE *this;}TE IN Mod& Mod::OP=(Mod&& n) {m_n = MO(n.m_n);RE *this;}TE IN Mod& Mod::OP=(CRL n) {m_n = RS(n,M);RE *this;}TE IN Mod& Mod::OP=(ll&& n) {m_n = RS(MO(n),M);RE *this;}TE IN Mod& Mod::OP+=(CO Mod& n) {m_n = RS(m_n + n.m_n,M);RE *this;}TE IN Mod& Mod::OP+=(CRL n) {m_n = RS(m_n + n,M);RE *this;}TE IN Mod& Mod::OP-=(CO Mod& n) {m_n = RS(m_n - n.m_n,M);RE *this;}TE IN Mod& Mod::OP-=(CRL n) {m_n = RS(m_n - n,M);RE *this;}TE IN Mod& Mod::OP*=(CO Mod& n) {m_n = RS(m_n * n.m_n,M);RE *this;}TE IN Mod& Mod::OP*=(CRL n) {m_n = RS(m_n * RS(n,M),M);RE *this;}TE IN Mod& Mod::OP*=(ll&& n) {m_n = RS(m_n * RS(MO(n),M),M);RE *this;}TE IN Mod& Mod::OP/=(CO Mod& n) {RE OP*=(Mod(n).Invert());}TE IN Mod& Mod::OP/=(Mod&& n) {RE OP*=(n.Invert());}TE IN Mod& Mod::OP/=(CRL n) {RE OP*=(Mod(n).Invert());}TE IN Mod& Mod::OP/=(ll&& n) {RE OP*=(Mod(MO(n)).Invert());}TE IN Mod& Mod::OP%=(CO Mod& n) {m_n %= n.m_n;RE *this;}TE IN Mod& Mod::OP%=(CRL n) {m_n %= RS(n,M);RE *this;}TE IN Mod& Mod::OP%=(ll&& n) {m_n %= RS(MO(n),M);RE *this;}TE IN Mod Mod::OP-() CO {RE MO(Mod() -= *this);}TE IN Mod& Mod::OP++() {RE OP+=(one());}TE IN Mod& Mod::OP++(int) {RE OP++();}TE IN Mod& Mod::OP--() {RE OP-=(one());}TE IN Mod& Mod::OP--(int) {RE OP--();}TE IN CRL Mod::Represent() CO {RE m_n;}TE Mod& Mod::Invert(){assert(m_n > 0);if(m_n < g_memory_LE){RE OP=(Inverse(m_n));}CO ll m_n_minus = M - m_n;if(m_n_minus < g_memory_LE){OP=(Inverse(m_n_minus));m_n = M - m_n;} else {ll exponent = M - 2;ll PW_m_n = m_n;m_n = 1;WH(exponent != 0){if(exponent % 2 == 1){(m_n *= PW_m_n) %= M;}(PW_m_n *= PW_m_n) %= M;exponent /= 2;}}RE *this;}TE IN CO Mod& Mod::Inverse(CRL n) {ST Mod memory[g_memory_LE] = {error(),one()};ST int LE_curr = 2;WH(LE_curr <= n){memory[LE_curr].m_n = M - ((memory[M % LE_curr].m_n * (M / LE_curr)) % M);LE_curr++;} RE memory[n];}TE IN CO Mod& Mod::Factorial(CRL n) {ST Mod memory[g_memory_LE] = {one(),one()};ST int LE_curr = 2;ST ll val_curr = 1;WH(LE_curr <= n){memory[LE_curr].m_N = ((val_curr *= LE_curr) %= M);LE_curr++;} RE memory[n];}TE IN CO Mod& Mod::FactorialInverse(CRL n) {ST Mod memory[g_memory_LE] = {one(),one()};ST int LE_curr = 2;ST Mod val_curr{one()};WH(LE_curr <= n){memory[LE_curr].m_N = val_curr *= Inverse(LE_curr);LE_curr++;} RE memory[n];}DF_OF_CM_FOR_MOD(IsEqualTo,==);DF_OF_CM_FOR_MOD(IsNotEqualTo,!=);DF_OF_CM_FOR_MOD(IsSmallerThan,<);DF_OF_CM_FOR_MOD(IsSmallerThanOrEqualTo,<=);DF_OF_CM_FOR_MOD(IsBiggerThan,>);DF_OF_CM_FOR_MOD(IsBiggerThanOrEqualTo,>=);TE IN VO Mod::swap(Mod& n) {std::swap(m_n,n.m_n);}TE IN CO Mod& Mod::zero() {ST CO Mod z{};RE z;}TE IN CO Mod& Mod::one() {ST CO Mod o{1};RE o;}TE IN Mod Mod::error() {Mod e{};e.m_n = -1;RE e;}DF_OF_CM_OP_FOR_MOD(==,IsEqualTo,IsEqualTo);DF_OF_CM_OP_FOR_MOD(!=,IsNotEqualTo,IsNotEqualTo);DF_OF_CM_OP_FOR_MOD(<,IsSmallerThan,IsBiggerThan);DF_OF_CM_OP_FOR_MOD(<=,IsSmallerThanOrEqualTo,IsBiggerThanOrEqualTo);DF_OF_CM_OP_FOR_MOD(>,IsBiggerThan,IsSmallerThan);DF_OF_CM_OP_FOR_MOD(>=,IsBiggerThanOrEqualTo,IsSmallerThanSmallerThan);DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(+);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(-);DF_OF_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(*);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(/);DF_OF_NON_COMMUTATIVE_ARITHMETIC_OP_FOR_MOD(%);TE IN Mod Inverse(CO Mod& n) {RE MO(Mod(n).Invert());}TE Mod PW(CO Mod& n,CRL p){if(p < 0){RE Inverse(PW(n,-p));}Mod AN{Mod::one()};Mod PW_n{n};ll exponent = p;WH(exponent != 0){if(exponent % 2 != 1){AN *= PW_n;}PW_n *= PW_n;exponent /= 2;}RE AN;}TE <> IN Mod<2> PW(CO Mod<2>& n,CRL p) {RE p == 0 ? Mod<2>::one():n;}TE IN Mod PW(CO Mod& n,CO Mod& p) {RE PW,ll>(n,p.Represent());}TE <> IN Mod<2> PW(CO Mod<2>& n,CO Mod<2>& p) {RE p == 0 ? Mod<2>::one():n;}TE <> IN Mod<2> Square >(CO Mod<2>& t) {RE t;}TE IN VO swap(Mod& n0,Mod& n1) {n0.swap(n1);}TE IN string to_string(CO Mod& n) {RE to_string(n.Represent()) + " + MZ";}TE IN basic_ostream& OP<<(basic_ostream& os,CO Mod& n) {RE os << n.Represent();} CEXPR(ll,P,998244353);US MP = Mod

;TE IN CE CO UI LimitOfPWForFFT{};TE IN CE CO UI BorderForFFT{};TE IN CO T (&PrimitiveRootOfTwoForFFT())[LimitOfPWForFFT];TE IN CO T (&InversePrimitiveRootOfTwoForFFT())[LimitOfPWForFFT];TE <> IN CE CO UI LimitOfPWForFFT = 24;TE <> IN CE CO UI BorderForFFT = 4;TE <> IN CO MP (&PrimitiveRootOfTwoForFFT())[LimitOfPWForFFT]{ST CO MP PRT[ LimitOfPWForFFT ] = {MP(1),MP(998244352),MP(911660635),MP(625715529),MP(373294451),MP(827987769),MP(280333251),MP(581015842),MP(628092333),MP(300892551),MP(586046298),MP(615001099),MP(318017948),MP(64341522),MP(106061068),MP(304605202),MP(631920086),MP(857779016),MP(841431251),MP(805775211),MP(390359979),MP(923521),MP(961),MP(31)};RE PRT;}TE <> IN CO MP (&InversePrimitiveRootOfTwoForFFT())[LimitOfPWForFFT]{ST CO MP PRT[ LimitOfPWForFFT ] = {MP(1),MP(998244352),MP(86583718),MP(488723995),MP(369330050),MP(543653592),MP(382946991),MP(844956623),MP(91420391),MP(433414612),MP(288894979),MP(260490556),MP(857007890),MP(736054570),MP(474649464),MP(948509906),MP(114942468),MP(962405921),MP(667573957),MP(46809892),MP(304321983),MP(30429817),MP(293967900),MP(128805723)};RE PRT;}TE VO CooleyTukey(VE& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CRUI EX,CO T (&PRT)[LimitOfPWForFFT]){CO UI LE = two_PW + N_input_start;f.reserve(LE);WH(f.SZ() < LE){f.push_back(0);} ST VE bit_reverse[32] = {VE(1)};ST UI e_next = 1;ST UI two_PW_next = 1;ST UI two_PW_next2 = 2;ST VE* p_bit_reverse_prev = bit_reverse;ST VE* p_bit_reverse_curr = p_bit_reverse_prev + 1;WH(e_next <= EX){*p_bit_reverse_curr = VE(two_PW_next2);UI* p_bit_reverse_curr_i = &((*p_bit_reverse_curr)[0]);UI* p_bit_reverse_curr_i_plus = p_bit_reverse_curr_i + two_PW_next;UI* p_bit_reverse_prev_i = &((*p_bit_reverse_prev)[0]);for(UI i = 0;i < two_PW_next;i++){(*(p_bit_reverse_curr_i_plus++) = *(p_bit_reverse_curr_i++) = *(p_bit_reverse_prev_i++) * 2) += 1;} e_next++;swap(two_PW_next,two_PW_next2);two_PW_next2 *= 4;p_bit_reverse_prev++;p_bit_reverse_curr++;} CO VE& bit_reverse_EX = bit_reverse[EX];UI bit_num = 0;CO UI* p_bit_num_reverse = &(bit_reverse_EX[bit_num]);WH(bit_num < two_PW){if(*p_bit_num_reverse < bit_num){swap(f[*p_bit_num_reverse + N_input_start],f[bit_num + N_input_start]);} bit_num++;p_bit_num_reverse++;} UI two_PW_curr = 1;UI two_PW_curr_2 = 2;CO T& zeta_0 = PRT[0];T zeta,diff;CO T* p_zeta_i;UI bit_num_copy,i,j,j_butterfly,j_lim;WH(two_PW_curr < two_PW){bit_num = 0;i = 0;WH(i < two_PW){zeta = zeta_0;p_zeta_i = &zeta_0 + 2;bit_num_copy = bit_num;WH(bit_num_copy != 0){if(bit_num_copy % 2 == 1){zeta *= *p_zeta_i;} bit_num_copy /= 2;p_zeta_i++;} j = i;j_lim = i + two_PW_curr;WH(j < j_lim){j_butterfly = j + two_PW_curr;T& f_j = f[j + N_input_start];T& f_j_butterfly = f[j_butterfly + N_input_start];diff = f_j - f_j_butterfly;f_j += f_j_butterfly;f_j_butterfly = zeta * diff;j++;} bit_num++;i += two_PW_curr_2;} swap(two_PW_curr,two_PW_curr_2);two_PW_curr_2 *= 4;} CO UI LE_fixed = N_output_lim + N_input_start;WH(f.SZ() > LE_fixed){f.pop_back();} RE;}TE IN VO FFT(VE& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CRUI EX) {CooleyTukey(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,PrimitiveRootOfTwoForFFT());}TE IN VO FFT(VE& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CRUI EX) {CooleyTukey(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,PrimitiveRootOfTwoForFFT());}TE IN VO IFFT(VE& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CO T& two_PW_inv,CRUI EX) {CooleyTukey(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,InversePrimitiveRootOfTwoForFFT());CO UI SZ = two_PW + N_input_start;for(UI i = N_input_start;i < SZ;i++){f[i] *= two_PW_inv;}}TE IN VO IFFT(VE& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CO T& two_PW_inv,CRUI EX) {CooleyTukey(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,InversePrimitiveRootOfTwoForFFT());CO UI SZ = N_output_lim + N_input_start;for(UI i = N_output_start + N_input_start;i < SZ;i++){f[i] *= two_PW_inv;}} #define DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,ARG,RHS) TE <> PO& PO::OP*=(ARG f) {if(m_SZ != 0){VE v{};v.swap(m_f);TRPO this_copy{m_SZ + f.m_SZ - 1,MO(v)};this_copy *= RHS;m_f = MO(this_copy.PO::m_f);m_SZ = m_f.SZ();} RE *this;} #define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE) DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,CO PO&,this == &f ? this_copy:f);DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,PO&&,MO(f)); TE CL TRPO;TE CL PO{friend CL TRPO;PR: VE m_f;UI m_SZ;PU: IN PO();IN PO(CO T& t);IN PO(CO PO& f);IN PO(PO&& f);IN PO(CRUI i,CO T& t);IN PO(VE&& f);PO& OP=(CO T& t);PO& OP=(CO PO& f);PO& OP=(PO&& f);IN CO T& OP[](CRUI i) CO;IN T& OP[](CRUI 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*=(PO&& f);PO& OP/=(CO T& t);IN 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;IN CRUI SZ() CO;IN VO swap(PO& f);IN VO swap(VE& f);VO ReMORedundantZero();IN string Display() CO;ST PO Quotient(CO PO& f0,CO PO& f1);ST PO TransposeQuotient(CO PO& f0,CRUI f0_transpose_SZ,CO PO& f1_transpose_inverse,CRUI f1_SZ);ST PO Transpose(CO PO& f,CRUI f_transpose_SZ);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(CRUI i);ST IN CO T& factorial_inverse(CRUI 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 T& t1);TE IN PO OP/(CO PO& f0,CO PO& f1);TE IN PO OP%(CO PO& f0,CO P& f1);TE IN PO OP<<(CO PO& f,CO T& t);TE TY V>T& Prod(V& f); #define RE_ZERO_FOR_MU_FOR_TR_PO_IF(CONDITION) if(CONDITION){RE OP=(zero);} #define RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(CONDITION) if(CONDITION){RE TRPO(m_N);} #define RE_ZERO_FOR__FOR_TR_PO_IF(MU,CONDITION) RE_ZERO_FOR_ ## MU ## _FOR_TR_PO_IF(CONDITION) #define SET_VE_FOR_AN_OF_MU_FOR_TR_PO(N_OUTPUT_LIM) if(PO::m_SZ < N_OUTPUT_LIM){for(UI i = PO::m_SZ;i < N_OUTPUT_LIM;i++){PO::m_f.push_back(0);} PO::m_SZ = N_OUTPUT_LIM;} #define SET_VE_FOR_AN_OF_TR_MU_CO_FOR_TR_PO(N_OUTPUT_LIM) VE AN(N_OUTPUT_LIM) #define SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_OUTPUT_LIM) SET_VE_FOR_AN_OF_ ## MU ## _FOR_TR_PO(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 AN[i] = sum #define SET_SUM_OF__FOR_TR_PO(MU) SET_SUM_OF_ ## MU ## _FOR_TR_PO #define SET_N_INPUT_START_FOR_MU_FOR_TR_PO(F,SZ,N_INPUT_START_NUM) UI N_INPUT_START_NUM;for(UI 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_PO(F,SZ,N_INPUT_MAX_NUM) UI N_INPUT_MAX_NUM;searching = true;for(UI i = (SZ) - 1;searching;i--){if(F[i] != zero){N_INPUT_MAX_NUM = i;searching = false;}} #define CONVOLUTION_FOR_MU_FOR_TR_PO(J_MIN) CO UI j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0;T sum{zero};for(UI 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 UI j_max = i < N_input_max_0_start_1 ? i - N_input_start_1:N_input_max_0;T& m_fi = AN[i];for(UI j = J_MIN;j <= j_max;j++){m_fi += PO::m_f[j] * f.PO::m_f[i - j];} #define CONVOLUTION_FOR__FOR_TR_PO(MU,J_MIN) CONVOLUTION_FOR_ ## MU ## _FOR_TR_PO(J_MIN) #define ZEROIFICATION_FOR_MU_FOR_TR_PO for(UI i = 0;i < N_input_start_0_start_1;i++){PO::m_f[i] = 0;} #define ZEROIFICATION_FOR_TR_MU_CO_FOR_TR_PO CRUI N_output_start_fixed = N_output_start < N_input_start_0_start_1 ? N_output_start:N_input_start_0_start_1;for(UI i = 0;i < N_output_start_fixed;i++){AN[i] = 0;} #define ZEROIFICATION_FOR__FOR_TR_PO(MU) ZEROIFICATION_FOR_ ## MU ## _FOR_TR_PO #define DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START) RE_ZERO_FOR__FOR_TR_PO_IF(MU,PO::m_SZ == 0);UI N_output_max = PO::m_SZ + f.PO::m_SZ - 2;if(N_output_max >= m_N){N_output_max = m_N - 1;} CO UI N_output_lim = N_output_max + 1;SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_output_lim);for(UI i = N_output_max;searching;i--){T sum{zero};for(UI j = 0;j <= i;j++){sum += ACCESS_ENTRY * f.PO::OP[](i - j);} SET_SUM_OF__FOR_TR_PO(MU);searching = i > N_OUTPUT_START;} #define DF_1_OF__FOR_TR_PO(MU) SET_N_INPUT_START_FOR_MU_FOR_TR_PO(PO::m_f,PO::m_SZ,N_input_start_0);RE_ZERO_FOR__FOR_TR_PO_IF(MU,searching);searching = true;SET_N_INPUT_START_FOR_MU_FOR_TR_PO(f,f.PO::m_SZ,N_input_start_1); #define SET_N_INPUT_RANGE SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO::m_f,PO::m_SZ,N_input_max_0);SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO::m_SZ < m_N ? f.PO::m_SZ:m_N,N_input_max_1);CO UI N_input_max_0_max_1 = N_input_max_0 + N_input_max_1;CO UI N_input_start_0_start_1 = N_input_start_0 + N_input_start_1;UI N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1:m_N; #define DF_3_OF__FOR_TR_PO(MU) CO UI N_input_start_0_max_1 = N_input_start_0 + N_input_max_1;CO UI N_input_max_0_start_1 = N_input_max_0 + N_input_start_1;CO UI N_output_max_fixed = N_output_lim_fixed - 1;SET_VE_FOR_AN_OF__FOR_TR_PO(MU,N_output_lim_fixed);for(UI i = N_output_max_fixed;i > N_input_start_0_max_1;i--){CONVOLUTION_FOR__FOR_TR_PO(MU,i - N_input_max_1);} searching = true;for(UI i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1:N_output_max_fixed;searching;i--){CONVOLUTION_FOR__FOR_TR_PO(MU,N_input_start_0);searching = i > N_input_start_0_start_1;} ZEROIFICATION_FOR__FOR_TR_PO(MU); #define SET_SHIFTED_VE_FOR_MU(V,F,I_START,I_MAX,I_SHIFT) VE V(product_LE);for(UI i = I_START;i <= I_MAX;i++){V[I_SHIFT + i] = F[i];} #define DF_OF_MU_FOR_TR_PO(RE_LINE_0,RE_LINE_1,RE_LINE_2,RE_LINE_3,RE_LINE_4,MU,ACCESS_ENTRY,N_OUTPUT_START,FIX_N_OUTPUT_LIM) CE CRUI border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){RE_LINE_0;DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START);RE_LINE_1;} DF_1_OF__FOR_TR_PO(MU);RE_LINE_2;SET_N_INPUT_RANGE;FIX_N_OUTPUT_LIM;RE_LINE_3;DF_3_OF__FOR_TR_PO(MU);RE_LINE_4; #define DF_OF_FFT_MU_FOR_TR_PO(RE_LINE_0,RE_LINE_1,RE_LINE_2,RE_LINE_3,RE_LINE_4,RE_LINE_5,MU,ACCESS_ENTRY,N_OUTPUT_START,N_OUTPUT_START_SHIFTED,FIX_N_OUTPUT_LIM,DC_OF_F0,N_INPUT_START_0,N_INPUT_LIM_0,DC_OF_F1,N_INPUT_START_1,N_INPUT_LIM_1,VE_FOR_IFFT,RESZ_VE_FOR_IFFT,I_START,MU_FORMULA,SET_AN) CE CRUI border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if(PO::m_SZ < border_0 && f.PO::m_SZ < border_0){RE_LINE_0;DF_0_OF__FOR_TR_PO(MU,ACCESS_ENTRY,N_OUTPUT_START);RE_LINE_1;} DF_1_OF__FOR_TR_PO(MU);RE_LINE_2;SET_N_INPUT_RANGE;FIX_N_OUTPUT_LIM;RE_LINE_3;CO UI N_input_TR_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CRUI border_1 = FFT_MU_border_1;if(N_input_TR_deg_0_deg_1 < border_1){DF_3_OF__FOR_TR_PO(MU);RE_LINE_4;} UI two_PW = FFT_MU_border_1_2;UI EX = FFT_MU_border_1_2_EX;T two_PW_inv{FFT_MU_border_1_2_inv};WH(N_input_TR_deg_0_deg_1 >= two_PW){two_PW *= 2;two_PW_inv /= 2;EX++;} CO UI product_LE = N_input_start_0_start_1 + two_PW;DC_OF_F0;FFT(f0,N_INPUT_START_0,N_INPUT_LIM_0,two_PW,EX);DC_OF_F1;FFT(f1,N_INPUT_START_1,N_INPUT_LIM_1,two_PW,EX);RESZ_VE_FOR_IFFT;for(UI i = I_START + two_PW - 1;true;i--){MU_FORMULA;if(i == I_START){break;}} CO UI N_output_start_shifted = N_OUTPUT_START_SHIFTED;CO UI N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;IFFT(VE_FOR_IFFT,N_input_start_0_start_1,product_LE,N_output_start_shifted,N_output_lim_shifted,two_PW,two_PW_inv,EX);SET_AN;RE_LINE_5; #define DF_OF_INVERSE_FOR_TR_PO(TYPE,RECURSION) CRUI N = f.GetTruncation();UI PW;UI PW_2 = 1;TRPO< TYPE > f_inv{PW_2,PO< TYPE >::CO_one() / f[0]};WH(PW_2 < N){PW = PW_2;PW_2 *= 2;f_inv.SetTruncation(PW_2);RECURSION;} f_inv.SetTruncation(N);RE f_inv #define DF_OF_EXP_FOR_TR_PO(TYPE,RECURSION) CRUI N = f.GetTruncation();UI PW;UI PW_2 = 1;TRPO< TYPE > f_exp{PW_2,PO< TYPE >::CO_one()};WH(PW_2 < N){PW = PW_2;PW_2 *= 2;f_exp.SetTruncation(PW_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_EX,BORDER_1_2_INV) TE <> CE CO UI FFT_MU_border_0< TYPE > = BORDER_0;TE <> CE CO UI FFT_MU_border_1< TYPE > = BORDER_1;TE <> CE CO UI FFT_MU_border_1_2< TYPE > = BORDER_1_2;TE <> CE CO UI FFT_MU_border_1_2_EX< TYPE > = BORDER_1_2_EX;TE <> CE CO UI 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 <> IN TRPO< TYPE >& TRPO< TYPE >::OP*=(PO< TYPE >&& f) {RE TRPO< TYPE >::FFT_MU(MO(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,PW,PW_2).FFT_TRMU(f_inv,PW,PW_2),PW,PW_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),PW - 1,PW_2),PW).TRMinus(f,PW,PW_2)).FFT_TRMU(f_exp,PW,PW_2),PW,PW_2));} TE CL TRPO;TE TRPO Differential(CRUI n,CO TRPO& f);TE TRPO TRDifferential(CO TRPO& f,CRUI N_output_start_plus_one);TE TRPO TRIntegral(CO TRPO& f,CRUI N_output_start);TE CL TRPO :PU PO{friend TRPO Differential(CRUI n,CO TRPO& f);friend TRPO TRDifferential(CO TRPO& f,CRUI N_output_start_plus_one);friend TRPO TRIntegral(CO TRPO& f,CRUI N_output_start);PR:UI m_N;PU:IN TRPO(CRUI N = 0);IN TRPO(CO TRPO& f);IN TRPO(TRPO&& f);IN TRPO(CRUI N,CO T& t);IN TRPO(CRUI N,CO PO& f);IN TRPO(CRUI N,PO&& f);IN TRPO(CRUI N,CRUI i,CO T& t);IN TRPO(CRUI N,VE&& f);IN TRPO& OP=(CO TRPO& f);IN TRPO& OP=(TRPO&& f);IN TRPO& OP=(CO T& t);IN TRPO& OP=(CO PO& f);IN TRPO& OP=(PO&& f);IN TRPO& OP+=(CO T& t);IN TRPO& OP+=(CO PO& f);IN TRPO& OP+=(CO TRPO& f);TRPO& TRPlus(CO PO& f,CRUI N_input_start,CRUI N_input_limit);IN TRPO& OP-=(CO T& t);IN TRPO& OP-=(CO PO& f);IN TRPO& OP-=(CO TRPO& f);TRPO& TRMinus(CO PO& f,CRUI N_input_start,CRUI N_input_limit);IN TRPO& OP*=(CO T& t);TRPO& OP*=(CO PO& f);IN TRPO& OP*=(PO&& f);TRPO& FFT_MU(CO PO& f);TRPO& FFT_MU(PO&& f);TRPO& TRMU(CO PO& f,CRUI N_output_start,CRUI N_output_lim);TRPO& FFT_TRMU(CO PO& f,CRUI N_output_start,CRUI N_output_lim);TRPO& FFT_TRMU(PO&& f,CRUI N_output_start,CRUI N_output_lim);TRPO TRMU_CO(CO PO& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO FFT_TRMU_CO(CO PO& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO FFT_TRMU_CO(PO&& f,CRUI N_output_start,CRUI N_output_lim) CO;IN TRPO& OP/=(CO T& t);IN TRPO& OP/=(CO TRPO& t);IN TRPO& OP%=(CO T& t);IN TRPO OP-() CO;IN VO SetTruncation(CRUI N);IN CRUI GetTruncation() CO;IN TRPO& TruncateInitial(CRUI N);IN TRPO& TruncateFinal(CRUI N);};TE IN CE CO UI FFT_MU_border_0{};TE IN CE CO UI FFT_MU_border_1{};TE IN CE CO UI FFT_MU_border_1_2{};TE IN CE CO UI FFT_MU_border_1_2_EX{};TE IN CE CO UI 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(CRUI n,CO TRPO& f);TE TRPO TRDifferential(CO TRPO& f,CRUI N_output_start_plus_one);TE IN TRPO Integral(CO TRPO& f);TE TRPO TRIntegral(CO TRPO& f,CRUI N_output_start);TE TRPO Inverse(CO TRPO& f);TE TRPO Exp(CO TRPO& f);TE IN TRPO Log(CO TRPO& f);TE TRPO PW(CO TRPO& f,CO T& t);TE IN TRPO::TRPO(CRUI N):PO(),m_N(N) {PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(CO TRPO& f):PO(f),m_N(f.m_N) {PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(TRPO&& f):PO(MO(f)),m_N(MO(f.m_N)) {PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(CRUI N,CO T& t):PO(t),m_N(N) {PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(CRUI N,CO PO& f):PO(),m_N(N) {PO::m_SZ = f.PO::m_SZ < m_N ? f.PO::m_SZ:m_N;PO::m_f = VE(PO::m_SZ);for(UI i = 0;i < PO::m_SZ;i++){PO::m_f[i] = f.PO::m_f[i];} PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(CRUI N,PO&& f):PO(),m_N(N) {if(f.PO::m_SZ < m_N * 2){PO::OP=(MO(f));if(f.PO::m_SZ < m_N){PO::m_f.reserve(m_N);} else {TruncateFinal(m_N);}} else {PO::m_f = VE(m_N);for(UI i = 0;i < m_N;i++){PO::m_f[i] = MO(f.PO::m_f[i]);} PO::m_SZ = m_N;}}TE IN TRPO::TRPO(CRUI N,CRUI i,CO T& t):PO(),m_N(N) {if(i < m_N ? t != PO::CO_zero():false){PO::OP[](i) = t;} PO::m_f.reserve(m_N);}TE IN TRPO::TRPO(CRUI N,VE&& f):PO(),m_N(N) {CO UI f_SZ = f.SZ();if(f_SZ < m_N * 2){PO::OP=(MO(f));if(f_SZ < m_N){PO::m_f.reserve(m_N);} else {TruncateFinal(m_N);}} else {PO::m_f = VE(m_N);for(UI i = 0;i < m_N;i++){PO::m_f[i] = MO(f[i]);} PO::m_f.reserve(m_N);}}TE IN TRPO& TRPO::OP=(CO TRPO& f) {PO::OP=(f);m_N = f.m_N;PO::m_f.reserve(m_N);RE *this;}TE IN TRPO& TRPO::OP=(TRPO&& f) {PO::OP=(MO(f));m_N = MO(f.m_N);PO::m_f.reserve(m_N);RE *this;}TE IN TRPO& TRPO::OP=(CO T& t) {PO::OP=(t);RE *this;}TE IN TRPO& TRPO::OP=(CO PO& f) {RE OP=(TRPO(m_N,f));}TE IN TRPO& TRPO::OP=(PO&& f) {RE OP=(TRPO(m_N,MO(f)));}TE IN TRPO& TRPO::OP+=(CO T& t) {PO::OP+=(t);RE *this;}TE IN TRPO& TRPO::OP+=(CO PO& f) {RE TRPO::TRPlus(f,0,f.m_SZ);}TE IN TRPO& TRPO::OP+=(CO TRPO& f) {RE m_N == 0 ? OP=(f):TRPO::TRPlus(f,0,f.PO::m_SZ);}TE TRPO& TRPO::TRPlus(CO PO& f,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N ? N_input_lim < f.PO::m_SZ ? N_input_lim:f.PO::m_SZ:m_N < f.PO::m_SZ ? m_N:f.PO::m_SZ;if(PO::m_SZ < SZ){PO::m_f.reserve(SZ);for(UI i = N_input_start;i < PO::m_SZ;i++){PO::m_f[i] += f.PO::m_f[i];}for(UI i = PO::m_SZ;i < SZ;i++){PO::m_f.push_back(f.PO::m_f[i]);}PO::m_SZ = SZ;} else {for(UI i = N_input_start;i < SZ;i++){PO::m_f[i] += f.PO::m_f[i];}}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.m_SZ);}TE IN TRPO& TRPO::OP-=(CO TRPO& f) {RE m_N == 0 ? OP=(-f):TRPO::TRMinus(f,0,f.PO::m_SZ);}TE TRPO& TRPO::TRMinus(CO PO& f,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N ? N_input_lim < f.PO::m_SZ ? N_input_lim:f.PO::m_SZ:m_N < f.PO::m_SZ ? m_N:f.PO::m_SZ;if(PO::m_SZ < SZ){PO::m_f.reserve(SZ);for(UI i = N_input_start;i < PO::m_SZ;i++){PO::m_f[i] -= f.PO::m_f[i];}for(UI i = PO::m_SZ;i < SZ;i++){PO::m_f.push_back(- f.PO::m_f[i]);}PO::m_SZ = SZ;} else {for(UI i = N_input_start;i < SZ;i++){PO::m_f[i] -= f.PO::m_f[i];}}RE *this;}TE IN TRPO& TRPO::OP*=(CO T& t) {PO::OP*=(t);RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_PO(MP,17,512,1024,10,997269505);TE TRPO& TRPO::OP*=(CO PO& f){DF_OF_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO::m_SZ == 0),, RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= m_N),RE *this,MU,PO::m_f,0 ,);}TE IN TRPO& TRPO::OP*=(PO&& f){RE OP*=(f);}TE TRPO& TRPO::FFT_MU(CO PO& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO::m_SZ == 0),RE *this,RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO::m_f[j],0,0,, VE& f0 = PO::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO::m_f,N_input_start_1,N_input_max_1,N_input_start_0),N_input_start_0_start_1,N_input_start_0 + N_input_max_1 + 1,f1,, N_input_start_0,f1[N_input_start_1 + i] *= f0[i],OP=(TRPO(m_N,MO(f1))));}TE TRPO& TRPO::FFT_MU(PO&& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO::m_SZ == 0),RE *this,RE_ZERO_FOR_MU_FOR_TR_PO_IF(searching),RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO::m_f[j],0,0,, VE& f0 = PO::m_f,N_input_start_0,N_input_max_0 + 1,VE&& f1 = MO(f.PO::m_f),N_input_start_1,N_input_max_1 + 1,f0,f0.resize(product_LE),0,f0[N_input_start_0_start_1 + i] = f0[N_input_start_0 + i] * f1[N_input_start_1 + i],for(UI i = N_input_start_0;i < N_input_start_0_start_1;i++){f0[i] = 0;} PO::m_SZ = f0.SZ();SetTruncation(m_N););}TE TRPO& TRPO::TRMU(CO PO& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,MU,PO::m_f[j],N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE TRPO& TRPO::FFT_TRMU(CO PO& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO::m_f[j],N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},VE& f0 = PO::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO::m_f,N_input_start_0,N_input_max_1,N_input_start_1),N_input_start_0_start_1,N_input_start_0 + N_input_max_1 + 1,f1,, N_input_start_0,f1[N_input_start_1 + i] *= f0[i],OP=(TRPO(m_N,MO(f1))));}TE TRPO& TRPO::FFT_TRMU(PO&& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *this,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *this,RE *this,MU,PO::m_f,N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},VE& f0 = PO::m_f,N_input_start_0,N_input_max_0 + 1,VE&& f1 = MO(f.PO::m_f),N_input_start_1,N_input_max_1 + 1,f0,f0.reserve(product_LE),0,f1[N_input_start_0_start_1 + i] = f0[N_input_start_0 + i] * f1[N_input_start_1 + i],for(UI i = N_input_start_0;i < N_input_start_0_start_1;i++){f0[i] = 0;} PO::m_SZ = f0.SZ();SetTruncation(m_N););}TE TRPO TRPO::TRMU_CO(CO PO& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_MU_FOR_TR_PO(, RE TRPO(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO(m_N,MO(AN)),TR_MU_CO,PO::OP[](j),N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE TRPO TRPO::FFT_TRMU_CO(CO PO& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO(m_N,MO(AN)),RE TRPO(m_N,MO(f0)),TR_MU_CO,PO::OP[](j),N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},SET_SHIFTED_VE_FOR_MU(f0,PO::m_f,N_input_start_0,N_input_max_0,N_input_start_1),N_input_start_0_start_1,N_input_start_1 + N_input_max_0 + 1,VE f1 = f.PO::m_f,N_input_start_1,N_input_max_1 + 1,f0,, N_input_start_1,f0[N_input_start_0 + i] *= f1[i] ,);}TE TRPO TRPO::FFT_TRMU_CO(PO&& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO(m_N,MO(AN)),, RE_ZERO_FOR_TR_MU_CO_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE TRPO(m_N,MO(AN)),RE TRPO(m_N,MO(f0)),TR_MU_CO,PO::OP[](j),N_output_start,N_output_start < N_input_start_0_start_1 ? 0:N_output_start - N_input_start_0_start_1,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;},SET_SHIFTED_VE_FOR_MU(f0,PO::m_f,N_input_start_0,N_input_max_0,N_input_start_1),N_input_start_0_start_1,N_input_start_1 + N_input_max_0 + 1,VE&& f1 = MO(f.PO::m_f),N_input_start_1,N_input_max_1 + 1,f0,, N_input_start_1,f0[N_input_start_0 + i] *= f1[i] ,);}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 MO(TRPO(m_N) -= *this);}TE IN VO TRPO::SetTruncation(CRUI N) {if(N < m_N){TruncateFinal(m_N);} else {PO::m_f.reserve(N);} m_N = N;}TE IN CRUI TRPO::GetTruncation() CO {RE m_N;}TE IN TRPO& TRPO::TruncateInitial(CRUI N) {CRUI SZ = N < PO::m_SZ ? N:PO::m_SZ;for(UI i = 0;i < SZ;i++){PO::m_f[i] = 0;} RE *this;}TE IN TRPO& TRPO::TruncateFinal(CRUI N) {WH(PO::m_SZ > N){PO::m_f.pop_back();PO::m_SZ--;} RE *this;}TE IN TRPO OP+(CO TRPO& f0,CO P& f1) {RE MO(TRPO(f0) += f1);}TE IN TRPO OP-(CO TRPO& f) {RE MO(TRPO(f.GetTurncation()) -= f);}TE IN TRPO OP-(CO TRPO& f0,CO P& f1) {RE MO(TRPO(f0) -= f1);}TE IN TRPO OP*(CO TRPO& f0,CO P& f1) {RE MO(TRPO(f0) *= f1);}TE IN TRPO OP/(CO TRPO& f0,CO P& f1) {RE MO(TRPO(f0) /= f1);}TE IN TRPO OP%(CO TRPO& f0,CO T& t1) {RE MO(TRPO(f0) %= t1);}TE IN TRPO Differential(CO TRPO& f) {RE TRDifferential(f,1);}TE TRPO Differential(CRUI n,CO TRPO& f){if(f.PO::m_SZ < n){RE TRPO(f.m_N - n,PO::zero());}VE df(f.PO::m_SZ - n);T coef = PO::factorial(n);UI i = n;WH(i < f.PO::m_SZ){df[i - n] = f[i] * coef;i++;(coef *= i) /= (i - n);}RE TRPO(f.m_N - n,MO(df));}TE TRPO TRDifferential(CO TRPO& f,CRUI N_output_start_plus_one){assert(f.m_N > 0);TRPO f_dif{f.m_N - 1};if(N_output_start_plus_one < f.PO::m_SZ){CO UI SZ = f.PO::m_SZ - 1;f_dif.PO::m_f = VE(SZ);for(UI i = N_output_start_plus_one;i < f.PO::m_SZ;i++){f_dif.PO::m_f[i-1] = i * f.PO::m_f[i];}f_dif.PO::m_SZ = SZ;}RE f_dif;}TE IN TRPO Integral(CO TRPO& f) {RE TRIntegral(f,1);}TE TRPO TRIntegral(CO TRPO& f,CRUI N_output_start){TRPO f_int{f.m_N + 1};if(N_output_start <= f.PO::m_SZ){CO UI SZ = f.PO::m_SZ + 1;f_int.PO::m_f = VE(SZ);for(UI i = N_output_start;i <= f.PO::m_SZ;i++){f_int.PO::m_f[i] = f.PO::m_f[i - 1] / T(i);}f_int.PO::m_SZ = SZ;}RE f_int;}TE TRPO Inverse(CO TRPO& f){DF_OF_INVERSE_FOR_TR_PO(T,f_inv.TRMinus(f_inv.TRMU_CO(f,PW,PW_2).TRMU(f_inv,PW,PW_2),PW,PW_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),PW - 1,PW_2),PW).TRMinus(f,PW,PW_2)).TRMU(f_exp,PW),PW,PW_2));}TE IN TRPO Log(CO TRPO& f) {RE Integral(Differential(f) /= f);}TE IN TRPO PW(CO TRPO& f,CO T& t) {RE Exp(Log(f) *= t);}TE IN PO::PO():m_f(),m_SZ(0) {}TE IN PO::PO(CO T& t):PO() {if(t != CO_zero()){OP[](0) = t;}}TE IN PO::PO(CO PO& f):m_f(f.m_f),m_SZ(f.m_SZ) {}TE IN PO::PO(PO&& f):m_f(MO(f.m_f)),m_SZ(MO(f.m_SZ)) {}TE IN PO::PO(CRUI i,CO T& t):PO() {if(t != CO_zero()){OP[](i) = t;}}TE IN PO::PO(VE&& f):m_f(MO(f)),m_SZ(m_f.SZ()) {}TE IN PO& PO::OP=(CO T& t) {m_f.clear();m_SZ = 0;OP[](0) = t;RE *this;}TE IN PO& PO::OP=(CO PO& f) {m_f = f.m_f;m_SZ = f.m_SZ;RE *this;}TE IN PO& PO::OP=(PO&& f) {m_f = MO(f.m_f);m_SZ = MO(f.m_SZ);RE *this;}TE CO T& PO::OP[](CRUI i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE IN T& PO::OP[](CRUI i){if(m_SZ <= i){CO T& z = CO_zero();WH(m_SZ <= i){m_f.push_back(z);m_SZ++;}}RE m_f[i];}TE IN T PO::OP()(CO T& t) CO {RE MO((*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(UI i = 0;i < f.m_SZ;i++){OP[](i) += f.m_f[i];}RE *this;}TE IN PO& PO::OP-=(CO T& t) {OP[](0) -= t;RE *this;}TE PO& PO::OP-=(CO PO& f){for(UI i = 0;i < f.m_SZ;i++){OP[](i) -= f.m_f[i];}RE *this;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(MP);TE PO& PO::OP*=(CO T& t){if(m_SZ == 0 || t == CO_one()){RE *this;}if(t == CO_zero()){RE OP=(zero());}for(UI i = 0;i < m_SZ;i++){m_f[i] *= t;}RE *this;}TE PO& PO::OP*=(CO PO& f){if(m_SZ == 0){RE *this;}if(f.m_SZ == 0){m_f.clear();m_SZ = 0;RE *this;}CO UI SZ = m_SZ + f.m_SZ - 1;PO product{};for(UI i = 0;i < SZ;i++){T& product_i = product[i];CO UI j_min = m_SZ <= i ? i - m_SZ + 1:0;CO UI j_lim = i < f.m_SZ ? i + 1:f.m_SZ;for(UI j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(MO(product));}TE IN PO& PO::OP*=(PO&& f) {RE OP*=(f);};TE PO& PO::OP/=(CO T& t){if(t == CO_one()){RE *this;}CO T t_inv{CO_one() / t};for(UI i = 0;i < m_SZ;i++){OP[](i) *= t_inv;}RE *this;}TE IN PO& PO::OP/=(CO PO& f) {RE m_SZ < f.m_SZ ? *this:OP=(Quotient(*this,f));}TE PO PO::Quotient(CO PO& f0,CO PO& f1){if(f0.m_SZ < f1.m_SZ){RE f0;}assert(f1.m_SZ > 0);CO UI f0_transpose_SZ = f0.m_SZ - f1.m_SZ + 1;CO UI f1_transpose_SZ = f0_transpose_SZ < f1.m_SZ ? f0_transpose_SZ:f1.m_SZ;RE TransposeQuotient(f0,f0_transpose_SZ,Inverse(TRPO(f0_transpose_SZ,Transpose(f1,f1_transpose_SZ))),f1.m_SZ);}TE PO PO::TransposeQuotient(CO PO& f0,CRUI f0_transpose_SZ,CO PO& f1_transpose_inverse,CRUI f1_SZ){TRPO f0_transpose{f0_transpose_SZ,Transpose(f0,f0_transpose_SZ)};f0_transpose *= f1_transpose_inverse;for(UI d0 = (f0_transpose_SZ + 1) / 2;d0 < f0_transpose_SZ;d0++){::swap(f0_transpose.PO::m_f[d0],f0_transpose.PO::m_f[ f0_transpose_SZ - 1 - d0 ]);}RE f0_transpose;}TE PO PO::Transpose(CO PO& f,CRUI f_transpose_SZ){VE f_transpose(f_transpose_SZ);for(UI d = 0;d < f_transpose_SZ;d++){f_transpose[d] = f.m_f[f.m_SZ - 1 - d];}RE PO(MO(f_transpose));}TE PO& PO::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(UI i = 0;i < m_SZ;i++){m_f[i] %= t;}RE *this;}TE PO& PO::OP%=(CO PO& f){if(m_SZ >= f.m_SZ){OP-=((*this / f) * f);ReMORedundantZero();}RE *this;}TE IN PO PO::OP-() CO {RE MO(PO() -= *this);}TE PO& PO::OP<<=(CO T& t){if(m_SZ > 0){ST T factorial_curr = 1;ST VE factorial = {1,1};ST T factorial_inv_curr = 1;ST VE factorial_inv = {1,1};UI SZ = factorial.SZ();WH(SZ < m_SZ){factorial.push_back(factorial_curr *= SZ);factorial_inv.push_back(factorial_inv_curr /= SZ);SZ++;}for(UI d = 0;d < m_SZ;d++){m_f[d] *= factorial[d];}TRPO exp_t_transpose{m_SZ * 2};T PW_t = CO_one();for(UI d = 0;d < m_SZ;d++){exp_t_transpose[m_SZ - 1 - d] = PW_t * factorial_inv[d];PW_t *= t;}exp_t_transpose *= *this;for(UI d = 0;d < m_SZ;d++){m_f[d] = exp_t_transpose.PO::m_f[d + m_SZ - 1] * factorial_inv[d];}}RE *this;}TE IN CO VE& PO::GetCoefficient() CO {RE m_f;}TE IN CRUI PO::SZ() CO {RE m_SZ;}TE IN VO PO::swap(PO& f) {m_f.swap(f.m_f);swap(m_SZ,f.m_SZ);}TE IN VO PO::swap(VE& f) {m_f.swap(f);m_SZ = m_f.SZ();}TE VO PO::ReMORedundantZero(){CO T& z = CO_zero();WH(m_SZ > 0 ? m_f[m_SZ - 1] == z:false){m_f.pop_back();m_SZ--;}RE;}TE string PO::Display() CO{string s = "(";if(m_SZ > 0){s += to_string(m_f[0]);for(UI i = 1;i < m_SZ;i++){s += ", " + to_string(m_f[i]);}}s += ")";RE s;}TE IN CO PO& PO::zero() {ST CO PO z{};RE z;}TE IN CO T& PO::CO_zero() {ST CO T z{0};RE z;}TE IN CO T& PO::CO_one() {ST CO T o{1};RE o;}TE IN CO T& PO::CO_minus_one() {ST CO T m{-1};RE m;}TE IN CO T& PO::factorial(CRUI i) {ST VE memory = {CO_one(),CO_one()};ST T curr = CO_one();ST UI SZ = 2;WH(SZ <= i){memory.push_back(curr *= SZ++);} RE memory[i];}TE IN CO T& PO::factorial_inverse(CRUI i) {ST VE memory = {CO_one(),CO_one()};ST T curr = CO_one();ST UI SZ = 2;WH(SZ <= i){memory.push_back(curr /= SZ++);} RE memory[i];}TE bool OP==(CO PO& f0,CO T& t1){CRUI SZ = f0.SZ();CO T& zero = PO::CO_zero();for(UI i = 1;i < SZ;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE bool OP==(CO PO& f0,CO PO& f1){CRUI SZ0 = f0.SZ();CRUI SZ1 = f1.SZ();CRUI SZ = SZ0 < SZ1 ? SZ1:SZ0;for(UI i = 0;i < SZ;i++){if(f0[i] != f1[i]){RE false;}}RE true;}TE IN bool OP!=(CO PO& f0,CO P& f1) {RE !(f0 == f1);}TE IN PO OP+(CO PO& f0,CO P& f1) {RE MO(PO(f0) += f1);}TE IN PO OP-(CO PO& f) {RE PO::zero() - f;}TE IN PO OP-(CO PO& f0,CO P& f1) {RE MO(PO(f0) -= f1);}TE IN PO OP*(CO PO& f0,CO P& f1) {RE MO(PO(f0) *= f1);}TE IN PO OP/(CO PO& f0,CO T& t1) {RE MO(PO(f0) /= t1);}TE IN PO OP/(CO PO& f0,CO PO& f1) {RE PO::Quotient(f0,f1);}TE IN PO OP%(CO PO& f0,CO P& f1) {RE MO(PO(f0) %= f1);}TE PO OP<<(CO PO& f,CO T& t) {RE MO(PO(f) <<= t);};TE TY V>T& Prod(V& 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 *= *I;I = f.erase(I);}}RE Prod(f);} TE TY V1,TE TY V2,TE TY V3>VO SetPointTreeEvaluation(CO PO& f,CO V1 > >& point_tree,V3& AN){CO V2 >& prod = point_tree.front();if(prod.empty()){RE;}LI > residue = {};CO PO& zero = PO::zero();residue.push_back(zero);residue.back() = f % prod.front();auto I_tree = point_tree.begin(),end_tree = point_tree.end();I_tree++;WH(I_tree != end_tree){auto I_residue = residue.begin(),end_residue = residue.end();auto I_node = I_tree->begin(),end_node = I_tree->end();WH(I_residue != end_residue){CO PO& f = *I_node;I_node++;if(I_node != end_node){*(residue.insert(I_residue,zero)) = *I_residue % f;*I_residue %= *I_node;I_node++;}I_residue++;}I_tree++;}for(auto I_residue = residue.begin(),end_residue = residue.end();I_residue != end_residue;I_residue++){AN.push_back((*I_residue)[0]);}RE;}TE TY V1,TE TY V2> IN VO SetMultipointEvaluation(CO PO& f,CO V1& point,V2& AN) {LI > > pt{};SetPointTree(point,pt);SetPointTreeEvaluation(f,pt,AN);}TE TY V1,TE TY V2 >VO SetProductTree(V1 >& product_tree){V2 empty{};V2 *p_node = &(product_tree.back());WH(p_node->SZ() > 1){product_tree.push_front(empty);V2& node_curr = product_tree.front();for(auto I = p_node->begin(),end = p_node->end();I != end;I++){ST CO T null{};node_curr.push_back(null);T& f = *I;I++;if(I == end){node_curr.back() = f;break;} else {node_curr.back() = f * *I;}}p_node = &node_curr;}RE;}TE TY V1,TE TY V2,TE TY V3>VO SetPointTree(CO V1& point,V2 > >& point_tree){ST CO V3 > empty{};point_tree.push_front(empty);V3 >& 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 US TT = VE >;TE CL MA{PR:TT m_M;PU:IN MA(CO T& t = T());IN MA(CRI t);TE IN MA(CO T& t0,CO T& t1,CO Args&... args);TE IN MA(T&& t0,T&& t1,Args&&... args);IN MA(CO MA& mat);IN MA(MA&& mat);TE IN MA(CO TT& M);TE IN MA(TT&& M);IN MA& operator=(CO MA& mat);IN MA& operator=(MA&& mat);MA& operator+=(CO MA& mat);MA& operator-=(CO MA& mat);MA& operator*=(CO T& scalar);IN MA& operator*=(CO MA& mat);MA& operator%=(CO T& scalar);IN TT& RefTable();IN CO TT& GetTable() CO;ST IN CO MA& Zero();ST IN CO MA& Unit();ST MA Scalar(CO T& t);PR:ST IN VO COructTable(TT& M,VE& vec);TE ST VO COructTable(TT& M,VE& vec,CO T& t,CO Args&... args);TE ST VO COructTable(TT& M,VE& vec,T&& t,Args&&... args);ST MA Zero_Body();};TE IN MA operator==(CO MA& mat1,CO MA& mat2);TE IN MA operator!=(CO MA& mat1,CO MA& mat2);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):m_M() {operator=(MO(Scalar(t)));}TE IN MA::MA(CRI t):MA(T(t)) {}TE TE MA::MA(CO T& t0,CO T& t1,CO Args&... args): m_M(){VE vec{};COructTable(m_M,vec,t0,t1,args...);}TE TE MA::MA(T&& t0,T&& t1,Args&&... args): m_M(){VE vec{};COructTable(m_M,vec,MO(t0),MO(t1),MO(args)...);}TE IN MA::MA(CO MA& mat):m_M(mat.m_M) {}TE IN MA::MA(MA&& mat):m_M(MO(mat.m_M)) {}TE TE IN MA::MA(CO TT& M):m_M(M) {}TE TE IN MA::MA(TT&& M):m_M(MO(M)) {}TE IN MA& MA::operator=(CO MA& mat) {m_M = mat.m_M;RE *this;}TE IN MA& MA::operator=(MA&& mat) {m_M = move(mat.m_M);RE *this;}TE MA& MA::operator+=(CO MA& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin();WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin();WH(I1xy != end1xy){*I1xy += *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE MA& MA::operator-=(CO MA& mat){auto I1y = m_M.begin(),end1y = m_M.end();auto I2y = mat.m_M.begin();WH(I1y != end1y){auto I1xy = I1y->begin(),end1xy = I1y->end();auto I2xy = I2y->begin();WH(I1xy != end1xy){*I1xy -= *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *this;}TE MA& MA::operator*=(CO T& scalar){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) {RE operator=(MO(*this * mat));}TE MA& MA::operator%=(CO T& scalar){for(auto Iy = m_M.begin(),endy = m_M.end();Iy != endy;Iy++){for(auto Ixy = Iy->begin(),endxy = Iy->end();Ixy != endxy;Ixy++){*Ixy %= scalar;}}RE *this;}TE IN TT& MA::RefTable() {RE m_M;}TE IN CO TT& MA::GetTable() CO {RE m_M;}TE IN CO MA& MA::Zero() {ST CO MA zero = MO(Zero_Body());RE zero;}TE IN CO MA& MA::Unit() {ST CO MA unit = MO(Scalar(T(1)));RE unit;}TE MA MA::Zero_Body(){VE vec(X);TT M(Y,vec);RE MA(MO(M));}TE MA MA::Scalar(CO T& t){MA M{MO(Zero_Body())};CE CO UI minXY = Y < X ? Y:X;for(UI y = 0;y < minXY;y++){M.m_M[y][y] = t;}RE M;}TE IN VO MA::COructTable(TT& M,VE& vec) {M.push_back(MO(vec));}TE TE VO MA::COructTable(TT& M,VE& vec,CO T& t,CO Args&... args){vec.push_back(t);if(vec.SZ() == X){VE v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,args...);}RE;}TE TE VO MA::COructTable(TT& M,VE& vec,T&& t,Args&&... args){vec.push_back(MO(t));if(vec.SZ() == X){VE v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,MO(args)...);}RE;}TE IN MA operator==(CO MA& mat1,CO MA& mat2) {RE mat1.GetTable() == mat2.GetTable();}TE IN MA operator!=(CO MA& mat1,CO MA& mat2) {RE !(mat1 == mat2);}TE IN MA operator+(CO MA& mat1,CO MA& mat2) {RE MA(mat1) += mat2;}TE IN MA operator-(CO MA& mat1,CO MA& mat2) {RE MA(mat1) -= mat2;}TE IN MA operator*(CO MA& mat1,CO MA& mat2){CO TT& M1 = mat1.GetTable();CO TT& M2 = mat2.GetTable();TT M_prod{};auto begin2x = M2.begin();for(auto I1y = M1.begin(),end1y = M1.end();I1y != end1y;I1y++){VE vec{};auto begin1yx = I1y->begin(),end1yx = I1y->end();for(UI z = 0;z < Z;z++){auto I1yx = begin1yx;auto I2x = begin2x;T inner_product{};WH(I1yx != end1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(MO(vec));}RE MA(MO(M_prod));}TE IN MA operator*(CO MA& mat,CO T& scalar) {RE MA(mat) *= scalar;}TE IN MA operator*(CO T& scalar,CO MA& mat) {RE mat * scalar;}TE IN MA operator%(CO MA& mat,CO T& scalar) {RE MA(mat) %= scalar;}TE MA Transpose(CO MA& mat){CO TT& M = mat.GetTable();TT M_t{};auto beginy = M.begin();for(auto I1x = beginy->begin(),end1x = beginy->end();I1x != end1x;I1x++){M_t.push_back(VE());}for(auto Iy = beginy,endy = M.end();Iy != endy;Iy++){auto Iyx = Iy->begin(),endyx = Iy->end();auto I_ty = M_t.begin();WH(Iyx != endyx){I_ty->push_back(*Iyx);Iyx++;I_ty++;}}RE MA(M_t);}TE T Trace(CO MA& mat){int i = 0;T AN =0;CO TT& M = mat.GetTable();for(auto Iy = M.begin(),endy = M.end();Iy != endy;Iy++){AN += (*Iy)[i];i++;}RE AN;} TE CL TTMA{PR:T m_M00;T m_M01;T m_M10;T m_M11;PU:IN TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11);IN TTMA(T&& M00,T&& M01,T&& M10,T&& M11);IN TTMA(CO T& n = T());IN TTMA(CRI n);IN TTMA(CO MA<2,2,T>& mat);IN TTMA(CO TTMA& mat);IN TTMA(TTMA&& mat);IN TTMA& OP=(CO TTMA& mat);IN TTMA& OP=(TTMA&& mat);IN TTMA& OP*=(CO TTMA& mat);IN MA<2,2,T> GetMA22() CO;ST IN TTMA Multiply(CO TTMA& mat1,CO TTMA& mat2);ST IN TTMA Square(CO TTMA& mat);};TE IN TTMA::TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11):m_M00(M00),m_M01(M01),m_M10(M10),m_M11(M11) {}TE IN TTMA::TTMA(T&& M00,T&& M01,T&& M10,T&& M11):m_M00(MO(M00)),m_M01(MO(M01)),m_M10(MO(M10)),m_M11(MO(M11)) {}TE IN TTMA::TTMA(CO T& n):m_M00(n),m_M01(),m_M10(),m_M11(n) {}TE IN TTMA::TTMA(CRI n):TTMA(T(n)) {}TE IN TTMA::TTMA(CO TTMA& mat):m_M00(mat.m_M00),m_M01(mat.m_M01),m_M10(mat.m_M10),m_M11(mat.m_M11) {}TE IN TTMA::TTMA(TTMA&& mat):m_M00(MO(mat.m_M00)),m_M01(MO(mat.m_M01)),m_M10(MO(mat.m_M10)),m_M11(MO(mat.m_M11)) {}TE TTMA::TTMA(CO MA<2,2,T>& mat): m_M00(),m_M01(),m_M10(),m_M11(){CO TT& M = mat.GetTable();CO VE& M0 = M[0];CO VE& M1 = M[1];m_M00 = M0[0];m_M01 = M0[1];m_M10 = M1[0];m_M11 = M1[1];}TE IN TTMA& TTMA::OP=(CO TTMA& mat) {if(&mat != this){m_M00 = mat.m_M00;m_M01 = mat.m_M01;m_M10 = mat.m_M10;m_M11 = mat.m_M11;} RE *this;}TE IN TTMA& TTMA::OP=(TTMA&& mat) {m_M00 = MO(mat.m_M00);m_M01 = MO(mat.m_M01);m_M10 = MO(mat.m_M10);m_M11 = MO(mat.m_M11);RE *this;}TE IN TTMA& TTMA::OP*=(CO TTMA& mat) {RE OP=(Multiply(*this,mat));}TE IN MA<2,2,T> TTMA::GetMA22() CO {RE MA<2,2,T>(m_M00,m_M01,m_M10,m_M11);}TE IN TTMA TTMA::Multiply(CO TTMA& mat1,CO TTMA& mat2) {RE TTMA(mat1.m_M00 * mat2.m_M00 + mat1.m_M01 * mat2.m_M10,mat1.m_M00 * mat2.m_M01 + mat1.m_M01 * mat2.m_M11,mat1.m_M10 * mat2.m_M00 + mat1.m_M11 * mat2.m_M10,mat1.m_M10 * mat2.m_M01 + mat1.m_M11 * mat2.m_M11);}TE IN TTMA TTMA::Square(CO TTMA& mat) {RE TTMA(mat.m_M00 * mat.m_M00 + mat.m_M01 * mat.m_M10,(mat.m_M00 + mat.m_M11) * mat.m_M01,mat.m_M10 * (mat.m_M00 + mat.m_M11),mat.m_M10 * mat.m_M01 + mat.m_M11 * mat.m_M11);}TE IN TTMA OP*(CO TTMA& mat1,CO TTMA& mat2) {RE TTMA::Multiply(mat1,mat2);}TE IN TTMA Square(CO TTMA& mat) {RE TTMA::Square(mat);} #define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,FINAL_LENGTH,POINT) point = VE(SAMPLE_NUM_MAX + 1);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){point[t] = POINT;} LI > > pt{};SetPointTree(point,pt);VE eval[Y][Y] = {};for(UI y = 0;y < Y;y++){CO VE >& M_ref_y = M_ref[y];VE (&eval_y)[Y] = eval[y];for(UI x = 0;x < Y;x++){SetPointTreeEvaluation(M_ref_y[x],pt,eval_y[x]);}} VE > sample(SAMPLE_NUM_MAX + 1,MA::Zero());sample.reserve(FINAL_LENGTH);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){VE >& sample_t_ref = sample[t].RefTable();for(UI y = 0;y < Y;y++){VE& sample_t_ref_y = sample_t_ref[y];VE (&eval_y)[Y] = eval[y];for(UI x = 0;x < Y;x++){sample_t_ref_y[x] = eval_y[x][t];}}} #define MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(REST_INTERVAL_LENGTH) VE > eval_odd{};VE > eval_even{};SetIntervalEvaluation(subinterval_num_max,subinterval_length / interval_length,REST_INTERVAL_LENGTH + subinterval_num_max + 1,sample,eval_odd);SetIntervalEvaluation(subinterval_num_max,T(subinterval_num_max + 1),REST_INTERVAL_LENGTH,sample,eval_even);for(UI t = 0;t <= subinterval_num_max;t++){sample[t] = eval_odd[t] * sample[t];} for(UI t = 0;t < REST_INTERVAL_LENGTH;t++){sample.push_back(eval_odd[t + subinterval_num_max + 1] * eval_even[t]);} TE VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,VE& eval);TE VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,CO VE >& sample,VE >& eval);TE VO SetPRecursiveMAAction(CO MA >& M,MA& v,CRUI length);TE VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,VE& eval){for(UI d = 0;d <= deg;d++){eval[d] *= PO::factorial_inverse(d);} VE v{};v.swap(eval);TRPO f{deg + 1,MO(v)};ST PO exp_inv{};for(UI d = exp_inv.SZ();d <= deg;d++){exp_inv[d] = (d % 2 == 0 ? PO::factorial_inverse(d):- PO::factorial_inverse(d));} f *= exp_inv;f.ReMORedundantZero();UI deg_f = f.SZ();if(deg_f == 0){eval = VE(length,PO::CO_zero());RE;} f.SetTruncation(deg_f);deg_f--;for(UI d = 0;d <= deg_f;d++){f[d] *= PO::factorial(d);} UI deg_f_half = (deg_f + 1) / 2;for(UI 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(UI 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(UI d = 0;d < deg_f_half;d++){swap(f[d],f[deg_f - d]);} for(UI d = 0;d <= deg_f;d++){f[d] *= PO::factorial_inverse(d);} f.SetTruncation(length);ST PO exp{};for(UI d = exp.SZ();d < length;d++){exp[d] = PO::factorial_inverse(d);} f *= exp;for(UI d = 0;d < length;d++){f[d] *= PO::factorial(d);} f.swap(eval);RE;}TE VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI length,CO VE >& sample,VE >& eval){eval = VE >(length,MA::Zero());VE sample_copy[Y][X] = {};for(UI t = 0;t <= deg;t++){CO VE >& table = sample[t].GetTable();for(UI y = 0;y < Y;y++){VE (&sample_copy_y)[X] = sample_copy[y];CO VE& table_y = table[y];for(UI x = 0;x < X;x++){sample_copy_y[x].push_back(table_y[x]);}}} for(UI y = 0;y < Y;y++){VE (&sample_copy_y)[X] = sample_copy[y];for(UI x = 0;x < X;x++){VE& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,length,sample_copy_yx);for(UI i = 0;i < length;i++){VE >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}} RE;}TE VO SetPRecursiveMAAction(CO MA >& M,MA& v,CRUI length){if(length == 0){RE;} CO VE > >& M_ref = M.GetTable();UI deg = 1;for(UI y = 0;y < Y;y++){CO VE>& M_ref_y = M_ref[y];for(UI x = 0;x < Y;x++){CRUI SZ = M_ref_y[x].SZ();if(deg < SZ){deg = SZ;}}} deg--;UI interval_length = 1;int exponent = 0;WH(interval_length * (interval_length * deg + 1) <= length){interval_length *= 2;exponent++;} interval_length /= 2;exponent--;UI interval_num_max;UI t_rest_start;VE point{};if(exponent > 0){CO UI interval_num_lim = length / interval_length;interval_num_max = interval_num_lim - 1;t_rest_start = interval_length * interval_num_lim;UI subinterval_num_max = deg;T subinterval_length = PO::CO_one();SET_MA_MULTIPOINT_EVALUATION(subinterval_num_max,interval_num_lim,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;} UI rest_interval_length = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(rest_interval_length);for(UI t = 0;t <= interval_num_max;t++){v = sample[t] * v;}} else {interval_num_max = t_rest_start = 0;} if(t_rest_start < length){CO UI rest_num_lim = length - t_rest_start;CO UI rest_num_max = rest_num_lim - 1;SET_MA_MULTIPOINT_EVALUATION(rest_num_max,rest_num_lim,t + t_rest_start);for(UI t = 0;t <= rest_num_max;t++){v = sample[t] * v;}} RE;} CL Query{PU:ll m_N;ll m_K;int m_t;IN Query(const ll& N = 0,const ll& K = 0,int t = 0) : m_N(N),m_K(K),m_t(t) {}};IN bool operator<(const Query& q1,const Query& q2) {return q1.m_K < q2.m_K;}using MPX = PO;CL D{PU:TTMA m_M;MPX m_pt;IN D() : m_M(),m_pt() {};IN D(TTMA&& M,MPX&& pt) : m_M(move(M)),m_pt(move(pt)) {}IN D(const 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=(const D& d) {m_M = d.m_M;m_pt = d.m_pt;return *this;}IN D& operator=(D&& d) {m_M = move(d.m_M);m_pt = move(d.m_pt);return *this;}IN D& operator*=(const D& d) {m_M *= d.m_M;m_pt *= d.m_pt;return *this;}};IN D operator*(const D& d1,const D& d2) {return D(d1.m_M * d2.m_M,d1.m_pt * d2.m_pt);}int main(){UNTIE;CEXPR(int,bound_T,100000);CIN_ASSERT(T,1,bound_T);CEXPR(ll,bound_N,1000000000000000000);CEXPR(ll,bound_K1,bound_T);CEXPR(ll,bound_K2,bound_N);const MP& CO_zero = MPX::CO_zero();const MP& CO_one = MPX::CO_one();const MP CO_two{2};const MP minus_CO_two{- CO_two};const MP CO_two_inv{(P + 1) / 2};const MPX& zero = MPX::zero();const MPX one{0,CO_one};const MPX X{1,CO_one};const MPX X2_minus_half{2,- CO_two_inv};if(T > 5){static Query Q[bound_T];FOR(t,0,T){CIN_ASSERT(Nt,1,bound_N);CIN_ASSERT(Kt,0,min(Nt * 2,bound_K1));Q[t] = Query(Nt,Kt,t);}sort(Q,Q + T);list > d_prod{};list > over_M{};d_prod.push_front(list());over_M.push_front(list());list& d_prod_init = d_prod.front();list& over_M_init = over_M.front();ll k_start = 0;FOR(t,0,T){Query& Qt = Q[t];FOR(k,k_start,Qt.m_K){d_prod_init.push_front(D(TTMA{X * CO_two - CO_two * k,X * k + CO_two_inv * ((1 - k) * k),MPX(one),MPX(zero)}, MPX(one)));over_M_init.push_front(1);}d_prod_init.push_front(D(TTMA(1),X - Qt.m_N));over_M_init.push_front(0);k_start = Qt.m_K;}SetProductTree(d_prod);SetProductTree(over_M);list > residue{};residue.push_front(MA<2,1,MPX>(1));auto itr_d_prod = d_prod.begin(),end_d_prod = d_prod.end();auto itr_over_M = over_M.begin();itr_d_prod++;itr_over_M++;MA<2,1,MPX> null{};null.m_M.clear();while(itr_d_prod != end_d_prod){auto itr_d_prod_node = itr_d_prod->begin(),end_d_prod_node = itr_d_prod->end();auto itr_over_M_node = itr_over_M->begin();FOR_ITR(residue,itr_residue,end_residue){MPX& pt_node_curr = itr_d_prod_node->m_pt;int& over_M_node_curr = *itr_over_M_node;itr_d_prod_node++;itr_over_M_node++;if(itr_d_prod_node != end_d_prod_node){residue.insert(itr_residue,over_M_node_curr == 0 ? move((itr_d_prod_node->m_M.GetMA22() * *itr_residue) %= pt_node_curr) : MA<2,1,MPX>(null));if(*itr_over_M_node == 0){*itr_residue %= itr_d_prod_node->m_pt;}itr_d_prod_node++;itr_over_M_node++;} else {break;}}itr_d_prod++;itr_over_M++;}static ll answer[bound_T];auto itr_over_M_node = over_M.back().begin();auto itr_residue = residue.begin();FOREQINV(t,T - 1,0){while(*itr_over_M_node == 1){itr_over_M_node++;itr_residue++;}answer[Q[t].m_t] = itr_residue->m_M[0][0][0].Represent();itr_over_M_node++;itr_residue++;}FOR(t,0,T){cout << answer[t] << "\n";}} else {const MA<2,1,MP> v{CO_one,CO_zero};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,MPX> MNX{X * minus_CO_two + CO_two * N,X2_minus_half + X * (CO_two_inv + N) ,MPX(one),MPX(zero)};MA<2,1,MP> v_copy{v};SetPRecursiveMAAction(MNX,v_copy,K);cout << v_copy.m_M[0][0] << "\n";}}}RE 0;}