#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO UI&
#define CRL CO ll&
US namespace std;US ll = long long;US UI = unsigned int;
#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) 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";
TE <TY INT1,TY INT2> IN INT1& RS(INT1& n,CO INT2& M) NE{RE n >= 0?n %= M:((((++n) *= -1) %= M) *= -1) += M - 1;}TE <TY INT1,TY INT2> IN INT1 RS(INT1&& n,CO INT2& M) NE{RE MO(RS(n,M));}TE <TY INT1,TY INT2> IN INT1 RS(CO INT1& n,CO INT2& M) NE{RE RS(MO(INT1(n)),M);}
#define SFINAE_TYPE_FOR_MOD(TYPE) decltype(int(decay_t<T>()),TYPE())
#define DC_OF_CM_FOR_MOD(FUNC) IN bool OP FUNC(CO Mod<M>& n) CO NE
#define DC_OF_AR_FOR_MOD(FUNC) IN Mod<M> OP FUNC(CO Mod<M>& n) CO NE;TE <TY T> IN SFINAE_TYPE_FOR_MOD(Mod<M>) OP FUNC(T&& n) CO NE;
#define DF_OF_CM_FOR_MOD(FUNC) TE <int M> IN bool Mod<M>::OP FUNC(CO Mod<M>& n) CO NE{RE m_n FUNC n.m_n;}
#define DF_OF_AR_FOR_MOD(FUNC,FORMULA) TE <int M> IN Mod<M> Mod<M>::OP FUNC(CO Mod<M>& n) CO NE{RE MO(Mod<M>(*TH) FUNC ## = n);}TE <int M> TE <TY T> IN SFINAE_TYPE_FOR_MOD(Mod<M>) Mod<M>::OP FUNC(T&& n) CO NE{RE FORMULA;}TE <int M,TY T> IN SFINAE_TYPE_FOR_MOD(Mod<M>) OP FUNC(T&& n0,CO Mod<M>& n1) NE{RE MO(Mod<M>(forward<T>(n0)) FUNC ## = n1);}
TE <int M>CL Mod{PU:int m_n;IN Mod() NE;IN Mod(CO Mod<M>& n) NE;IN Mod(Mod<M>& n) NE;IN Mod(Mod<M>&& n) NE;TE <TY T> IN Mod(T& n,SFINAE_TYPE_FOR_MOD(int) dummy = 0) NE;TE <TY T> IN Mod(T&& n,SFINAE_TYPE_FOR_MOD(int) dummy = 0) NE;IN Mod<M>& OP=(CO Mod<M>& n) NE;IN Mod<M>& OP+=(CO Mod<M>& n) NE;IN Mod<M>& OP-=(CO Mod<M>& n) NE;IN Mod<M>& OP*=(CO Mod<M>& n) NE;IN Mod<M>& OP/=(CO Mod<M>& n);IN Mod<M>& OP++() NE;IN Mod<M> OP++(int) NE;IN Mod<M>& OP--() NE;IN Mod<M> OP--(int) NE;DC_OF_CM_FOR_MOD(==);DC_OF_CM_FOR_MOD(!=);DC_OF_CM_FOR_MOD(<);DC_OF_CM_FOR_MOD(<=);DC_OF_CM_FOR_MOD(>);DC_OF_CM_FOR_MOD(>=);DC_OF_AR_FOR_MOD(+);DC_OF_AR_FOR_MOD(-);DC_OF_AR_FOR_MOD(*);DC_OF_AR_FOR_MOD(/);IN Mod<M> OP-() CO NE;IN Mod<M>& SignInvert() NE;IN Mod<M>& Invert();TE <TY T> IN Mod<M>& PositivePW(T&& EX) NE;TE <TY T> IN Mod<M>& PW(T&& EX);IN CO int& Represent() CO NE;IN VO swap(Mod<M>& n) NE;ST IN CO int& Inverse(CO int& n) NE;ST IN CO int& Factorial(CO int& n) NE;ST IN CO int& FactorialInverse(CO int& n) NE;ST IN CO Mod<M>& zero() NE;ST IN CO Mod<M>& one() NE;ST IN CE int BinaryDigitUpperBound() NE;ST IN CE ll MNBasePW(int&& EX) NE;ST CE CO int g_MN_digit = BinaryDigitUpperBound();ST CE CO ll g_MN_base = ll(1) << g_MN_digit;ST CE CO ll g_MN_base_minus = g_MN_base - 1;ST CE CO ll g_MN_M_negative_inverse = g_MN_base - MNBasePW((1 << (g_MN_digit - 1)) - 1);ST CE CO ll g_MN_base_square = (g_MN_base * g_MN_base) % M;ST CE CO int g_memory_bound = 1000000;ST CE CO int g_memory_LE = M < g_memory_bound?M:g_memory_bound;ST IN ll MNTranformation(CO int& n) NE;ST IN ll& MNReduction(ll& n) NE;ST IN int MNMU(CO int& n0,CO int& n1) NE;ST IN VO Normalise(int& n) NE;};TE <int M> Mod<M> IN Inverse(CO Mod<M>& n);TE <int M,TY T> IN Mod<M> PW(CO Mod<M>& n,CO T& EX);TE <TY T> IN Mod<2> PW(CO Mod<2>& n,CO T& p);TE <TY T> IN T Square(CO T& t);TE <> IN Mod<2> Square<Mod<2> >(CO Mod<2>& t);TE <int M> IN VO swap(Mod<M>& n0,Mod<M>& n1) NE;TE <int M> IN string to_string(CO Mod<M>& n) NE;TE<int M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n);
TE <int M> IN CE int Mod<M>::BinaryDigitUpperBound() NE{int AN = 0;ll PW = 1;WH(M > PW){AN++;PW <<= 1;}RE AN;}TE <int M> IN CE ll Mod<M>::MNBasePW(int&& EX) NE{ll prod = 1;ll PW = M;WH(EX != 0){if((EX & 1) == 1){(prod *= PW) &= g_MN_base_minus;}(PW *= PW) &= g_MN_base_minus;EX >>= 1;}RE prod;}TE <int M> IN ll Mod<M>::MNTranformation(CO int& n) NE{ll n_copy = n;RE MO(MNReduction(n_copy *= g_MN_base_square));}TE <int M> IN ll& Mod<M>::MNReduction(ll& n) NE{ll n_copy = n;RE ((n += (((n_copy &= g_MN_base_minus) *= g_MN_M_negative_inverse) &= g_MN_base_minus) *= M) >>= g_MN_digit) < M?n:n -= M;}TE <int M> IN int Mod<M>::MNMU(CO int& n0,CO int& n1) NE{ll n0_copy = n0;RE MNReduction(MNReduction(n0_copy *= n1) *= g_MN_base_square);}TE <int M> IN VO Mod<M>::Normalise(int& n) NE{if(n >= M){n -= M;}else if(n < 0){n += M;}}TE <int M> IN Mod<M>::Mod() NE:m_n(){}TE <int M> IN Mod<M>::Mod(CO Mod<M>& n) NE:m_n(n.m_n){}TE <int M> IN Mod<M>::Mod(Mod<M>& n) NE:m_n(n.m_n){}TE <int M> IN Mod<M>::Mod(Mod<M>&& n) NE:m_n(MO(n.m_n)){}TE <int M> TE<TY T> IN Mod<M>::Mod(T& n,SFINAE_TYPE_FOR_MOD(int) dummy) NE:m_n(RS(decay_t<T>(n),M)){}TE <int M> TE<TY T> IN Mod<M>::Mod(T&& n,SFINAE_TYPE_FOR_MOD(int) dummy) NE:m_n(RS(forward<T>(n),M)){}TE <int M> IN Mod<M>& Mod<M>::OP=(CO Mod<M>& n) NE{m_n = n.m_n;RE *TH;}TE <int M> IN Mod<M>& Mod<M>::OP+=(CO Mod<M>& n) NE{Normalise(m_n += n.m_n);RE *TH;}TE <int M> IN Mod<M>& Mod<M>::OP-=(CO Mod<M>& n) NE{Normalise(m_n -= n.m_n);RE *TH;}TE <int M> IN Mod<M>& Mod<M>::OP*=(CO Mod<M>& n) NE{m_n = MNMU(m_n,n.m_n);RE *TH;}TE <int M> IN Mod<M>& Mod<M>::OP/=(CO Mod<M>& n){RE OP*=(Mod<M>(n).Invert());}TE <int M> IN Mod<M>& Mod<M>::OP++() NE{RE OP+=(one());}TE <int M> IN Mod<M> Mod<M>::OP++(int) NE{Mod<M> n{*TH};OP++();RE n;}TE <int M> IN Mod<M>& Mod<M>::OP--() NE{RE OP-=(one());}TE <int M> IN Mod<M> Mod<M>::OP--(int) NE{Mod<M> n{*TH};OP--();RE n;}DF_OF_CM_FOR_MOD(==);DF_OF_CM_FOR_MOD(!=);DF_OF_CM_FOR_MOD(>);DF_OF_CM_FOR_MOD(>=);DF_OF_CM_FOR_MOD(<);DF_OF_CM_FOR_MOD(<=);DF_OF_AR_FOR_MOD(+,Mod<M>(forward<T>(n)) += *TH);DF_OF_AR_FOR_MOD(-,Mod<M>(forward<T>(n)).SignInvert() += *TH);DF_OF_AR_FOR_MOD(*,Mod<M>(forward<T>(n)) *= *TH);DF_OF_AR_FOR_MOD(/,Mod<M>(forward<T>(n)).Invert() *= *TH);TE <int M> IN Mod<M> Mod<M>::OP-() CO NE{RE MO(Mod<M>(*TH).SignInvert());}TE <int M> IN Mod<M>& Mod<M>::SignInvert() NE{if(m_n > 0){m_n = M - m_n;}RE *TH;}TE <int M> IN Mod<M>& Mod<M>::Invert(){assert(m_n > 0);if(m_n < g_memory_LE){m_n = Inverse(m_n);}else{CO int m_n_minus = M - m_n;if(m_n_minus < g_memory_LE){m_n = M - Inverse(m_n_minus);}else{RE PositivePW(M - 2);}}RE *TH;}TE <int M> TE <TY T> IN Mod<M>& Mod<M>::PositivePW(T&& EX) NE{ll prod = g_MN_base;ll PW = MNTranformation(m_n);WH(EX != 0){if((EX & 1) == 1){MNReduction(prod *= PW);}MNReduction(PW *= PW);EX >>= 1;}m_n = int(MNReduction(prod));RE *TH;}TE <int M> TE <TY T> IN Mod<M>& Mod<M>::PW(T&& EX){if(EX < 0){assert(m_n > 0);EX *= 2 - M;}EX %= M - 1;if(EX != 0){RE PositivePW(forward<T>(EX));}RE *TH;}TE <int M> IN CO int& Mod<M>::Inverse(CO int& n) NE{ST int memory[g_memory_LE] ={-1,1};ST int LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = M - MNMU(memory[M % LE_curr],M / LE_curr);LE_curr++;}RE memory[n];}TE <int M> IN CO int& Mod<M>::Factorial(CO int& n) NE{ST int memory[g_memory_LE] ={1,1};ST int LE_curr = 2;ST ll val_curr = g_MN_base;WH(LE_curr <= n){memory[LE_curr] = int(MNReduction(val_curr *= MNTranformation(LE_curr)));LE_curr++;}RE memory[n];}TE <int M> IN CO int& Mod<M>::FactorialInverse(CO int& n) NE{ST int memory[g_memory_LE] ={1,1};ST int LE_curr = 2;ST ll val_curr = g_MN_base;WH(LE_curr <= n){memory[LE_curr] = int(MNReduction(val_curr *= MNTranformation(Inverse(LE_curr))));LE_curr++;}RE memory[n];}TE <int M> IN CO int& Mod<M>::Represent() CO NE{RE m_n;}TE <int M> IN VO Mod<M>::swap(Mod<M>& n) NE{std::swap(m_n,n.m_n);}TE <int M> IN CO Mod<M>& Mod<M>::zero() NE{ST CO Mod<M> z{};RE z;}TE <int M> IN CO Mod<M>& Mod<M>::one() NE{ST CO Mod<M> o{1};RE o;}TE <int M> IN Mod<M> Inverse(CO Mod<M>& n){RE MO(Mod<M>(n).Invert());}TE <int M,TY T> IN Mod<M> PW(CO Mod<M>& n,CO T& EX){RE MO(Mod<M>(n).PW(T(EX)));}TE <TY T> IN Mod<2> PW(CO Mod<2>& n,CO T& EX){RE EX == 0?Mod<2>::one():n;}TE <> IN Mod<2> Square<Mod<2> >(CO Mod<2>& t){RE t;}TE <int M> IN VO swap(Mod<M>& n0,Mod<M>& n1) NE{n0.swap(n1);}TE <int M> IN string to_string(CO Mod<M>& n) NE{RE to_string(n.Represent()) + " + MZ";}TE<int M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n){RE os << n.Represent();}

TE <TY T>US TT = VE<VE<T> >;TE <UI Y,UI X,TY T>CL MA{PU:TT<T> m_M;IN MA(CO T& t = T()) NE;IN MA(CRI t) NE;TE <TY... Args> IN MA(CO T& t0,CO T& t1,CO Args&... args) NE;TE <TY... Args> IN MA(T&& t0,T&& t1,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>& OP=(CO MA<Y,X,T>& mat) NE;IN MA<Y,X,T>& OP=(MA<Y,X,T>&& mat) NE;MA<Y,X,T>& OP+=(CO MA<Y,X,T>& mat);MA<Y,X,T>& OP-=(CO MA<Y,X,T>& mat);MA<Y,X,T>& OP*=(CO T& scalar) NE;IN MA<Y,X,T>& OP*=(CO MA<X,X,T>& mat) NE;MA<Y,X,T>& OP%=(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;ST IN VO COructTable(TT<T>& M,VE<T>& vec) NE;TE <TY... Args> ST VO COructTable(TT<T>& M,VE<T>& vec,CO T& t,CO Args&... args) NE;TE <TY... Args> ST VO COructTable(TT<T>& M,VE<T>& vec,T&& t,Args&&... args) NE;ST MA<Y,X,T> Zero_Body() NE;};TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE;TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2);TE <UI Y,UI X,UI Z,TY T>MA<Y,Z,T> OP*(CO MA<Y,X,T>& mat1,CO MA<X,Z,T>& mat2);TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP*(CO MA<Y,X,T>& mat,CO T& scalar);TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP*(CO T& scalar,CO MA<Y,X,T>& mat);TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP%(CO MA<Y,X,T>& mat,CO T& scalar);TE <UI Y,UI X,TY T>MA<X,Y,T> Transpose(CO MA<Y,X,T>& mat);TE <UI X,TY T>T Trace(CO MA<X,X,T>& mat);
TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CO T& t) NE:m_M(){OP=(Scalar(t));}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CRI t) NE:MA(T(t)){}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO T& t0,CO T& t1,CO Args&... args) NE:m_M(){VE<T> vec{};COructTable(m_M,vec,t0,t1,args...);}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(T&& t0,T&& t1,Args&&... args) NE:m_M(){VE<T> vec{};COructTable(m_M,vec,MO(t0),MO(t1),MO(args)...);}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(CO MA<Y,X,T>& mat) NE:m_M(mat.m_M){}TE <UI Y,UI X,TY T> IN MA<Y,X,T>::MA(MA<Y,X,T>&& mat) NE:m_M(MO(mat.m_M)){}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(CO TT<T>& M) NE:m_M(M){}TE <UI Y,UI X,TY T> TE <TY... Args> IN MA<Y,X,T>::MA(TT<T>&& M) NE:m_M(MO(M)){}TE <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP=(CO MA<Y,X,T>& mat) NE{m_M = mat.m_M;RE *TH;}TE <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP=(MA<Y,X,T>&& mat) NE{m_M = MO(mat.m_M);RE *TH;}TE <UI Y,UI X,TY T>MA<Y,X,T>& MA<Y,X,T>::OP+=(CO MA<Y,X,T>& mat){auto I1y = m_M.BE(),EN1y = m_M.EN();auto I2y = mat.m_M.BE();WH(I1y != EN1y){auto I1xy = I1y->BE(),EN1xy = I1y->EN();auto I2xy = I2y->BE();WH(I1xy != EN1xy){*I1xy += *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *TH;}TE <UI Y,UI X,TY T>MA<Y,X,T>& MA<Y,X,T>::OP-=(CO MA<Y,X,T>& mat){auto I1y = m_M.BE(),EN1y = m_M.EN();auto I2y = mat.m_M.BE();WH(I1y != EN1y){auto I1xy = I1y->BE(),EN1xy = I1y->EN();auto I2xy = I2y->BE();WH(I1xy != EN1xy){*I1xy -= *I2xy;I1xy++;I2xy++;}I1y++;I2y++;}RE *TH;}TE <UI Y,UI X,TY T> MA<Y,X,T>& MA<Y,X,T>::OP*=(CO T& scalar) NE{for(auto Iy = m_M.BE(),ENy = m_M.EN();Iy != ENy;Iy++){for(auto Ixy = Iy->BE(),ENxy = Iy->EN();Ixy != ENxy;Ixy++){*Ixy *= scalar;}}RE *TH;}TE <UI Y,UI X,TY T> IN MA<Y,X,T>& MA<Y,X,T>::OP*=(CO MA<X,X,T>& mat) NE{RE OP=(MO(*TH * mat));}TE <UI Y,UI X,TY T> MA<Y,X,T>& MA<Y,X,T>::OP%=(CO T& scalar) NE{for(auto Iy = m_M.BE(),ENy = m_M.EN();Iy != ENy;Iy++){for(auto Ixy = Iy->BE(),ENxy = Iy->EN();Ixy != ENxy;Ixy++){*Ixy %= scalar;}}RE *TH;}TE <UI Y,UI X,TY T> IN TT<T>& MA<Y,X,T>::RefTable() NE{RE m_M;}TE <UI Y,UI X,TY T> IN CO TT<T>& MA<Y,X,T>::GetTable() CO NE{RE m_M;}TE <UI Y,UI X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Zero() NE{ST CO MA<Y,X,T> zero = MO(Zero_Body());RE zero;}TE <UI Y,UI X,TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Unit() NE{ST CO MA<Y,X,T> unit = MO(Scalar(T(1)));RE unit;}TE <UI Y,UI 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>(MO(M));}TE <UI Y,UI X,TY T>MA<Y,X,T> MA<Y,X,T>::Scalar(CO T& t) NE{MA<Y,X,T> 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 <UI Y,UI X,TY T> IN VO MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec) NE{M.push_back(MO(vec));}TE <UI Y,UI X,TY T> TE <TY... Args> VO 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 <UI Y,UI X,TY T> TE <TY... Args> VO MA<Y,X,T>::COructTable(TT<T>& M,VE<T>& vec,T&& t,Args&&... args) NE{vec.push_back(MO(t));if(vec.SZ() == X){VE<T> v{};v.swap(vec);COructTable(M,v);}if(M.SZ() < Y){COructTable(M,vec,MO(args)...);}RE;}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP==(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE{RE mat1.GetTable() == mat2.GetTable();}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP!=(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2) NE{RE !(mat1 == mat2);}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP+(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2){RE MA<Y,X,T>(mat1) += mat2;}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP-(CO MA<Y,X,T>& mat1,CO MA<Y,X,T>& mat2){RE MA<Y,X,T>(mat1) -= mat2;}TE <UI Y,UI X,UI Z,TY T> IN MA<Y,Z,T> OP*(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 BE2x = M2.BE();for(auto I1y = M1.BE(),EN1y = M1.EN();I1y != EN1y;I1y++){VE<T> vec{};auto BE1yx = I1y->BE(),EN1yx = I1y->EN();for(UI z = 0;z < Z;z++){auto I1yx = BE1yx;auto I2x = BE2x;T inner_product{};WH(I1yx != EN1yx){inner_product += (*I1yx) * (*I2x)[z];I1yx++;I2x++;}vec.push_back(inner_product);}M_prod.push_back(MO(vec));}RE MA<Y,Z,T>(MO(M_prod));}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP*(CO MA<Y,X,T>& mat,CO T& scalar){RE MA<Y,X,T>(mat) *= scalar;}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP*(CO T& scalar,CO MA<Y,X,T>& mat){RE mat * scalar;}TE <UI Y,UI X,TY T> IN MA<Y,X,T> OP%(CO MA<Y,X,T>& mat,CO T& scalar){RE MA<Y,X,T>(mat) %= scalar;}TE <UI Y,UI 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 BEy = M.BE();for(auto I1x = BEy->BE(),EN1x = BEy->EN();I1x != EN1x;I1x++){M_t.push_back(VE<T>());}for(auto Iy = BEy,ENy = M.EN();Iy != ENy;Iy++){auto Iyx = Iy->BE(),ENyx = Iy->EN();auto I_ty = M_t.BE();WH(Iyx != ENyx){I_ty->push_back(*Iyx);Iyx++;I_ty++;}}RE MA<X,Y,T>(M_t);}TE <UI 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.BE(),ENy = M.EN();Iy != ENy;Iy++){AN += (*Iy)[i];i++;}RE AN;}

TE <TY T>CL TTMA{PU:T m_M00;T m_M01;T m_M10;T m_M11;IN TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11) NE;IN TTMA(T&& M00,T&& M01,T&& M10,T&& M11) NE;IN TTMA(CO T& n = T()) NE;IN TTMA(CRI n) NE;IN TTMA(CO MA<2,2,T>& mat);IN TTMA(CO TTMA<T>& mat) NE;IN TTMA(TTMA<T>&& mat) NE;IN TTMA<T>& OP=(CO TTMA<T>& mat) NE;IN TTMA<T>& OP=(TTMA<T>&& mat) NE;IN TTMA<T>& OP*=(CO TTMA<T>& mat) NE;IN MA<2,2,T> GetMA22() CO NE;ST IN TTMA<T> Multiply(CO TTMA<T>& mat1,CO TTMA<T>& mat2);ST IN TTMA<T> Square(CO TTMA<T>& mat);};TE <TY T> IN TTMA<T> OP*(CO TTMA<T>& mat1,CO TTMA<T>& mat2);TE <TY T> IN TTMA<T> Square(CO TTMA<T>& mat);
TE <TY T> IN TTMA<T>::TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11) NE:m_M00(M00),m_M01(M01),m_M10(M10),m_M11(M11){}TE <TY T> IN TTMA<T>::TTMA(T&& M00,T&& M01,T&& M10,T&& M11) NE:m_M00(MO(M00)),m_M01(MO(M01)),m_M10(MO(M10)),m_M11(MO(M11)){}TE <TY T> IN TTMA<T>::TTMA(CO T& n) NE:m_M00(n),m_M01(),m_M10(),m_M11(n){}TE <TY T> IN TTMA<T>::TTMA(CRI n) NE:TTMA(T(n)){}TE <TY T> IN TTMA<T>::TTMA(CO TTMA<T>& mat) NE:m_M00(mat.m_M00),m_M01(mat.m_M01),m_M10(mat.m_M10),m_M11(mat.m_M11){}TE <TY T> IN TTMA<T>::TTMA(TTMA<T>&& mat) NE: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 <TY T>TTMA<T>::TTMA(CO MA<2,2,T>& mat): m_M00(),m_M01(),m_M10(),m_M11(){CO TT<T>& M = mat.GetTable();CO VE<T>& M0 = M[0];CO VE<T>& M1 = M[1];m_M00 = M0[0];m_M01 = M0[1];m_M10 = M1[0];m_M11 = M1[1];}TE <TY T> IN TTMA<T>& TTMA<T>::OP=(CO TTMA<T>& mat) NE{if(&mat != TH){m_M00 = mat.m_M00;m_M01 = mat.m_M01;m_M10 = mat.m_M10;m_M11 = mat.m_M11;}RE *TH;}TE <TY T> IN TTMA<T>& TTMA<T>::OP=(TTMA<T>&& mat) NE{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 *TH;}TE <TY T> IN TTMA<T>& TTMA<T>::OP*=(CO TTMA<T>& mat) NE{RE OP=(Multiply(*TH,mat));}TE <TY T> IN MA<2,2,T> TTMA<T>::GetMA22() CO NE{RE MA<2,2,T>(m_M00,m_M01,m_M10,m_M11);}TE <TY T> IN TTMA<T> TTMA<T>::Multiply(CO TTMA<T>& mat1,CO TTMA<T>& mat2){RE TTMA<T>(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 <TY T> IN TTMA<T> TTMA<T>::Square(CO TTMA<T>& mat){RE TTMA<T>(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 <TY T> IN TTMA<T> OP*(CO TTMA<T>& mat1,CO TTMA<T>& mat2){RE TTMA<T>::Multiply(mat1,mat2);}TE <TY T> IN TTMA<T> Square(CO TTMA<T>& mat){RE TTMA<T>::Square(mat);}

IN CEXPR(ll,P,998244353);US MP = Mod<P>;TE <TY T> IN CE CO UI LimitOfPWForFFT{};TE <TY T> IN CE CO UI BorderForFFT{};TE <TY T> IN CO T (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPWForFFT<T>];TE <TY T> IN CO T (&InversePrimitiveRootOfTwoForFFT() NE)[LimitOfPWForFFT<T>];TE <> IN CE CO UI LimitOfPWForFFT<MP > = 24;TE <> IN CE CO UI BorderForFFT<MP > = 4;TE <> IN CO MP (&PrimitiveRootOfTwoForFFT() NE)[LimitOfPWForFFT<MP >]{ST CO MP PRT[ LimitOfPWForFFT<MP > ] ={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() NE)[LimitOfPWForFFT<MP >]{ST CO MP PRT[ LimitOfPWForFFT<MP > ] ={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 <TY T>VO CooleyTukey(VE<T>& 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<T>]){CO UI LE = two_PW + N_input_start;f.reserve(LE);WH(f.SZ() < LE){f.push_back(0);}ST VE<UI> bit_reverse[32] ={VE<UI>(1)};ST UI e_next = 1;ST UI two_PW_next = 1;ST UI two_PW_next2 = 2;ST VE<UI>* p_bit_reverse_prev = bit_reverse;ST VE<UI>* p_bit_reverse_curr = p_bit_reverse_prev + 1;WH(e_next <= EX){*p_bit_reverse_curr = VE<UI>(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<UI>& 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 <TY T> IN VO FFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CRUI EX){CooleyTukey<T>(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,PrimitiveRootOfTwoForFFT<T>());}TE <TY T> IN VO FFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI N_output_start,CRUI N_output_lim,CRUI two_PW,CRUI EX){CooleyTukey<T>(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,PrimitiveRootOfTwoForFFT<T>());}TE <TY T> IN VO IFFT(VE<T>& f,CRUI N_input_start,CRUI N_input_lim,CRUI two_PW,CO T& two_PW_inv,CRUI EX){CooleyTukey<T>(f,N_input_start,N_input_lim,0,two_PW,two_PW,EX,InversePrimitiveRootOfTwoForFFT<T>());CO UI SZ = two_PW + N_input_start;for(UI i = N_input_start;i < SZ;i++){f[i] *= two_PW_inv;}}TE <TY T> IN VO IFFT(VE<T>& 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<T>(f,N_input_start,N_input_lim,N_output_start,N_output_lim,two_PW,EX,InversePrimitiveRootOfTwoForFFT<T>());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<TYPE>& PO<TYPE>::OP*=(ARG f){if(m_SZ != 0){VE<TYPE> v{};v.swap(m_f);TRPO<TYPE> TH_copy{m_SZ + f.m_SZ - 1,MO(v)};TH_copy *= RHS;m_f = MO(TH_copy.PO<TYPE>::m_f);m_SZ = m_f.SZ();}RE *TH;}
#define DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE) DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,CO PO<TYPE>&,TH == &f?TH_copy:f);DF_BODY_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(TYPE,PO<TYPE>&&,MO(f));
TE <TY T>CL PO{PU:VE<T> m_f;UI m_SZ;IN PO();IN PO(CO T& t);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(CRUI i,CO T& t);IN PO(CO VE<T>& f);IN PO(VE<T>&& f);IN PO<T>& OP=(CO T& t);IN PO<T>& OP=(CO PO<T>& f);IN PO<T>& OP=(PO<T>&& f);IN PO<T>& OP=(CO VE<T>& f);IN PO<T>& OP=(VE<T>&& f);IN CO T& OP[](CRUI i) CO;IN T& OP[](CRUI 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*=(PO<T>&& f);PO<T>& OP/=(CO T& t);IN 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 CRUI SZ() CO NE;IN VO swap(PO<T>& f);IN VO swap(VE<T>& f);VO ReMORedundantZero();IN string Display() CO NE;ST PO<T> Quotient(CO PO<T>& f0,CO PO<T>& f1);ST PO<T> TransposeQuotient(CO PO<T>& f0,CRUI f0_transpose_SZ,CO PO<T>& f1_transpose_inverse,CRUI f1_SZ);ST PO<T> Transpose(CO PO<T>& f,CRUI f_transpose_SZ);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(CRUI i);ST IN CO T& factorial_inverse(CRUI 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> IN PO<T> OP/(CO PO<T>& f0,CO T& t1);TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO PO<T>& 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,TE <TY> TY V>T& Prod(V<T>& 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<T>(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<T>::m_SZ < N_OUTPUT_LIM){for(UI 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_PO(N_OUTPUT_LIM) VE<T> 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<T>::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<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_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<T>::m_f[j] * f.PO<T>::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<T>::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<T>::m_SZ == 0);UI 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 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<T>::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<T>::m_f,PO<T>::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<T>::m_SZ,N_input_start_1);
#define SET_N_INPUT_RANGE SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(PO<T>::m_f,PO<T>::m_SZ,N_input_max_0);SET_N_INPUT_MAX_FOR_MU_FOR_TR_PO(f,f.PO<T>::m_SZ < m_N?f.PO<T>::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<T> 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<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_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<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_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<T>;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<T>;UI EX = FFT_MU_border_1_2_EX<T>;T two_PW_inv{FFT_MU_border_1_2_inv<T>};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<T>(f0,N_INPUT_START_0,N_INPUT_LIM_0,two_PW,EX);DC_OF_F1;FFT<T>(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<T>(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 <TY T>CL TRPO:PU PO<T>{PU:UI m_N;IN TRPO(CRUI N = 0);IN TRPO(CO TRPO<T>& f);IN TRPO(TRPO<T>&& f);IN TRPO(CRUI N,CO T& t);IN TRPO(CRUI N,CO PO<T>& f);IN TRPO(CRUI N,PO<T>&& f);IN TRPO(CRUI N,CRUI i,CO T& t);IN TRPO(CRUI N,VE<T>&& f);IN TRPO<T>& OP=(CO TRPO<T>& f);IN TRPO<T>& OP=(TRPO<T>&& f);IN TRPO<T>& OP=(CO T& t);IN TRPO<T>& OP=(CO PO<T>& f);IN TRPO<T>& OP=(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,CRUI N_input_start,CRUI 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,CRUI N_input_start,CRUI N_input_limit);IN TRPO<T>& OP*=(CO T& t);TRPO<T>& OP*=(CO PO<T>& f);IN TRPO<T>& OP*=(PO<T>&& f);TRPO<T>& FFT_MU(CO PO<T>& f);TRPO<T>& FFT_MU(PO<T>&& f);TRPO<T>& TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T>& FFT_TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T>& FFT_TRMU(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim);TRPO<T> TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO<T> FFT_TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO;TRPO<T> FFT_TRMU_CO(PO<T>&& f,CRUI N_output_start,CRUI 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 VO SetTruncation(CRUI N) NE;IN CRUI GetTruncation() CO NE;IN TRPO<T>& TruncateInitial(CRUI N) NE;IN TRPO<T>& TruncateFinal(CRUI N) NE;};TE <TY T> IN CE CO UI FFT_MU_border_0{};TE <TY T> IN CE CO UI FFT_MU_border_1{};TE <TY T> IN CE CO UI FFT_MU_border_1_2{};TE <TY T> IN CE CO UI FFT_MU_border_1_2_EX{};TE <TY T> IN CE CO UI 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(CRUI n,CO TRPO<T>& f);TE <TY T> TRPO<T> TRDifferential(CO TRPO<T>& f,CRUI 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,CRUI 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> PW(CO TRPO<T>& f,CO T& t);
TE <TY T> IN TRPO<T>::TRPO(CRUI N):PO<T>(),m_N(N){PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CO TRPO<T>& f):PO<T>(f),m_N(f.m_N){PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(TRPO<T>&& f):PO<T>(MO(f)),m_N(MO(f.m_N)){PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CO T& t):PO<T>(t),m_N(N){PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CO PO<T>& f):PO<T>(),m_N(N){PO<T>::m_SZ = f.PO<T>::m_SZ < m_N?f.PO<T>::m_SZ:m_N;PO<T>::m_f = VE<T>(PO<T>::m_SZ);for(UI i = 0;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] = f.PO<T>::m_f[i];}PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,PO<T>&& f):PO<T>(),m_N(N){if(f.PO<T>::m_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f.PO<T>::m_SZ < m_N){PO<T>::m_f.reserve(m_N);}else{TruncateFinal(m_N);}}else{PO<T>::m_f = VE<T>(m_N);for(UI i = 0;i < m_N;i++){PO<T>::m_f[i] = MO(f.PO<T>::m_f[i]);}PO<T>::m_SZ = m_N;}}TE <TY T> IN TRPO<T>::TRPO(CRUI N,CRUI i,CO T& t):PO<T>(),m_N(N){if(i < m_N?t != PO<T>::CO_zero():false){PO<T>::OP[](i) = t;}PO<T>::m_f.reserve(m_N);}TE <TY T> IN TRPO<T>::TRPO(CRUI N,VE<T>&& f):PO<T>(),m_N(N){CO UI f_SZ = f.SZ();if(f_SZ < m_N * 2){PO<T>::OP=(MO(f));if(f_SZ < m_N){PO<T>::m_f.reserve(m_N);}else{TruncateFinal(m_N);}}else{PO<T>::m_f = VE<T>(m_N);for(UI i = 0;i < m_N;i++){PO<T>::m_f[i] = MO(f[i]);}PO<T>::m_f.reserve(m_N);}}TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO TRPO<T>& f){PO<T>::OP=(f);m_N = f.m_N;PO<T>::m_f.reserve(m_N);RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP=(TRPO<T>&& f){PO<T>::OP=(MO(f));m_N = MO(f.m_N);PO<T>::m_f.reserve(m_N);RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP=(CO T& t){PO<T>::OP=(t);RE *TH;}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=(PO<T>&& f){RE OP=(TRPO<T>(m_N,MO(f)));}TE <TY T> IN TRPO<T>& TRPO<T>::OP+=(CO T& t){PO<T>::OP+=(t);RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP+=(CO PO<T>& f){RE TRPO<T>::TRPlus(f,0,f.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,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N?N_input_lim < f.PO<T>::m_SZ?N_input_lim:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ?m_N:f.PO<T>::m_SZ;if(PO<T>::m_SZ < SZ){PO<T>::m_f.reserve(SZ);for(UI i = N_input_start;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}for(UI i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(f.PO<T>::m_f[i]);}PO<T>::m_SZ = SZ;}else{for(UI i = N_input_start;i < SZ;i++){PO<T>::m_f[i] += f.PO<T>::m_f[i];}}RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP-=(CO T& t){PO<T>::OP-=(t);RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP-=(CO PO<T>& f){RE TRPO<T>::TRMinus(f,0,f.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,CRUI N_input_start,CRUI N_input_lim){CRUI SZ = N_input_lim < m_N?N_input_lim < f.PO<T>::m_SZ?N_input_lim:f.PO<T>::m_SZ:m_N < f.PO<T>::m_SZ?m_N:f.PO<T>::m_SZ;if(PO<T>::m_SZ < SZ){PO<T>::m_f.reserve(SZ);for(UI i = N_input_start;i < PO<T>::m_SZ;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}for(UI i = PO<T>::m_SZ;i < SZ;i++){PO<T>::m_f.push_back(- f.PO<T>::m_f[i]);}PO<T>::m_SZ = SZ;}else{for(UI i = N_input_start;i < SZ;i++){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}}RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::OP*=(CO T& t){PO<T>::OP*=(t);RE *TH;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TR_PO(MP,17,512,1024,10,997269505);TE <TY T>TRPO<T>& TRPO<T>::OP*=(CO PO<T>& f){DF_OF_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::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 *TH,MU,PO<T>::m_f,0,);}TE <TY T> IN TRPO<T>& TRPO<T>::OP*=(PO<T>&& f){RE OP*=(f);}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(CO PO<T>& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_SZ == 0),RE *TH,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 *TH,RE *TH,MU,PO<T>::m_f[j],0,0,, VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO<T>::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<T>(m_N,MO(f1))));}TE <TY T>TRPO<T>& TRPO<T>::FFT_MU(PO<T>&& f){DF_OF_FFT_MU_FOR_TR_PO(RE_ZERO_FOR_MU_FOR_TR_PO_IF(f.PO<T>::m_SZ == 0),RE *TH,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 *TH,RE *TH,MU,PO<T>::m_f[j],0,0,, VE<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,VE<T>&& f1 = MO(f.PO<T>::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<T>::m_SZ = f0.SZ();SetTruncation(m_N););}TE <TY T>TRPO<T>& TRPO<T>::TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_MU_FOR_TR_PO(, RE *TH,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *TH,MU,PO<T>::m_f[j],N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE <TY T>TRPO<T>& TRPO<T>::FFT_TRMU(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *TH,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *TH,RE *TH,MU,PO<T>::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<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,SET_SHIFTED_VE_FOR_MU(f1,f.PO<T>::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<T>(m_N,MO(f1))));}TE <TY T>TRPO<T>& TRPO<T>::FFT_TRMU(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim){DF_OF_FFT_MU_FOR_TR_PO(, RE *TH,, RE_ZERO_FOR_MU_FOR_TR_PO_IF(N_input_start_0_start_1 >= N_output_lim_fixed),RE *TH,RE *TH,MU,PO<T>::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<T>& f0 = PO<T>::m_f,N_input_start_0,N_input_max_0 + 1,VE<T>&& f1 = MO(f.PO<T>::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<T>::m_SZ = f0.SZ();SetTruncation(m_N););}TE <TY T>TRPO<T> TRPO<T>::TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_MU_FOR_TR_PO(, RE TRPO<T>(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<T>(m_N,MO(AN)),TR_MU_CO,PO<T>::OP[](j),N_output_start,if(N_output_lim_fixed > N_output_lim){N_output_lim_fixed = N_output_lim;});}TE <TY T>TRPO<T> TRPO<T>::FFT_TRMU_CO(CO PO<T>& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO<T>(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<T>(m_N,MO(AN)),RE TRPO<T>(m_N,MO(f0)),TR_MU_CO,PO<T>::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<T>::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<T> f1 = f.PO<T>::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 <TY T>TRPO<T> TRPO<T>::FFT_TRMU_CO(PO<T>&& f,CRUI N_output_start,CRUI N_output_lim) CO{DF_OF_FFT_MU_FOR_TR_PO(, RE TRPO<T>(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<T>(m_N,MO(AN)),RE TRPO<T>(m_N,MO(f0)),TR_MU_CO,PO<T>::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<T>::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<T>&& f1 = MO(f.PO<T>::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 <TY T> IN TRPO<T>& TRPO<T>::OP/=(CO T& t){PO<T>::OP/=(t);RE *TH;}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 *TH;}TE <TY T> IN TRPO<T> TRPO<T>::OP-() CO{RE MO(TRPO<T>(m_N) -= *TH);}TE <TY T> IN VO TRPO<T>::SetTruncation(CRUI N) NE{if(N < m_N){TruncateFinal(m_N);}else{PO<T>::m_f.reserve(N);}m_N = N;}TE <TY T> IN CRUI TRPO<T>::GetTruncation() CO NE{RE m_N;}TE <TY T> IN TRPO<T>& TRPO<T>::TruncateInitial(CRUI N) NE{CRUI SZ = N < PO<T>::m_SZ?N:PO<T>::m_SZ;for(UI i = 0;i < SZ;i++){PO<T>::m_f[i] = 0;}RE *TH;}TE <TY T> IN TRPO<T>& TRPO<T>::TruncateFinal(CRUI N) NE{WH(PO<T>::m_SZ > N){PO<T>::m_f.pop_back();PO<T>::m_SZ--;}RE *TH;}TE <TY T,TY P> IN TRPO<T> OP+(CO TRPO<T>& f0,CO P& f1){RE MO(TRPO<T>(f0) += f1);}TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f){RE MO(TRPO<T>(f.GetTurncation()) -= f);}TE <TY T,TY P> IN TRPO<T> OP-(CO TRPO<T>& f0,CO P& f1){RE MO(TRPO<T>(f0) -= f1);}TE <TY T,TY P> IN TRPO<T> OP*(CO TRPO<T>& f0,CO P& f1){RE MO(TRPO<T>(f0) *= f1);}TE <TY T,TY P> IN TRPO<T> OP/(CO TRPO<T>& f0,CO P& f1){RE MO(TRPO<T>(f0) /= f1);}TE <TY T> IN TRPO<T> OP%(CO TRPO<T>& f0,CO T& t1){RE MO(TRPO<T>(f0) %= t1);}TE <TY T> IN TRPO<T> Differential(CO TRPO<T>& f){RE TRDifferential<T>(f,1);}TE <TY T>TRPO<T> Differential(CRUI n,CO TRPO<T>& f){if(f.PO<T>::m_SZ < n){RE TRPO(f.m_N - n,PO<T>::zero());}VE<T> df(f.PO<T>::m_SZ - n);T coef = PO<T>::factorial(n);UI i = n;WH(i < f.PO<T>::m_SZ){df[i - n] = f[i] * coef;i++;(coef *= i) /= (i - n);}RE TRPO(f.m_N - n,MO(df));}TE <TY T>TRPO<T> TRDifferential(CO TRPO<T>& f,CRUI N_output_start_plus_one){assert(f.m_N > 0);TRPO<T> f_dif{f.m_N - 1};if(N_output_start_plus_one < f.PO<T>::m_SZ){CO UI SZ = f.PO<T>::m_SZ - 1;f_dif.PO<T>::m_f = VE<T>(SZ);for(UI i = N_output_start_plus_one;i < f.PO<T>::m_SZ;i++){f_dif.PO<T>::m_f[i-1] = i * f.PO<T>::m_f[i];}f_dif.PO<T>::m_SZ = SZ;}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,CRUI N_output_start){TRPO<T> f_int{f.m_N + 1};if(N_output_start <= f.PO<T>::m_SZ){CO UI SZ = f.PO<T>::m_SZ + 1;f_int.PO<T>::m_f = VE<T>(SZ);for(UI i = N_output_start;i <= f.PO<T>::m_SZ;i++){f_int.PO<T>::m_f[i] = f.PO<T>::m_f[i - 1] / T(i);}f_int.PO<T>::m_SZ = SZ;}RE f_int;}TE <TY T>TRPO<T> Inverse(CO TRPO<T>& 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 <TY T>TRPO<T> Exp(CO TRPO<T>& 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 <TY T> IN TRPO<T> Log(CO TRPO<T>& f){RE Integral<T>(Differential<T>(f) /= f);}TE <TY T> IN TRPO<T> PW(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(MO(f.m_f)),m_SZ(MO(f.m_SZ)){}TE <TY T> IN PO<T>::PO(CRUI i,CO T& t):PO(){if(t != CO_zero()){OP[](i) = t;}}TE <TY T> IN PO<T>::PO(CO VE<T>& f):m_f(f),m_SZ(m_f.SZ()){}TE <TY T> IN PO<T>::PO(VE<T>&& f):m_f(MO(f)),m_SZ(m_f.SZ()){}TE <TY T> IN PO<T>& PO<T>::OP=(CO T& t){m_f.clear();m_SZ = 0;OP[](0) = t;RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(CO PO<T>& f){m_f = f.m_f;m_SZ = f.m_SZ;RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(PO<T>&& f){m_f = MO(f.m_f);m_SZ = MO(f.m_SZ);RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(CO VE<T>& f){m_f = f;m_SZ = f.m_SZ;RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP=(VE<T>&& f){m_f = MO(f);m_SZ = m_f.SZ();RE *TH;}TE <TY T>CO T& PO<T>::OP[](CRUI i) CO{if(m_SZ <= i){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::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 <TY T> IN T PO<T>::OP()(CO T& t) CO{RE MO((*TH % (PO<T>(1,CO_one()) - t))[0]);}TE <TY T> IN PO<T>& PO<T>::OP+=(CO T& t){OP[](0) += t;RE *TH;}TE <TY T>PO<T>& PO<T>::OP+=(CO PO<T>& f){for(UI i = 0;i < f.m_SZ;i++){OP[](i) += f.m_f[i];}RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP-=(CO T& t){OP[](0) -= t;RE *TH;}TE <TY T>PO<T>& PO<T>::OP-=(CO PO<T>& f){for(UI i = 0;i < f.m_SZ;i++){OP[](i) -= f.m_f[i];}RE *TH;}DF_OF_PARTIAL_SPECIALISATION_OF_MU_OF_PO(MP);TE <TY T>PO<T>& PO<T>::OP*=(CO T& t){if(m_SZ == 0 || t == CO_one()){RE *TH;}if(t == CO_zero()){RE OP=(zero());}for(UI i = 0;i < m_SZ;i++){m_f[i] *= t;}RE *TH;}TE <TY T>PO<T>& PO<T>::OP*=(CO PO<T>& f){if(m_SZ == 0){RE *TH;}if(f.m_SZ == 0){m_f.clear();m_SZ = 0;RE *TH;}CO UI SZ = m_SZ + f.m_SZ - 1;PO<T> 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 <TY T> IN PO<T>& PO<T>::OP*=(PO<T>&& f){RE OP*=(f);};TE <TY T>PO<T>& PO<T>::OP/=(CO T& t){if(t == CO_one()){RE *TH;}CO T t_inv{CO_one() / t};for(UI i = 0;i < m_SZ;i++){OP[](i) *= t_inv;}RE *TH;}TE <TY T> IN PO<T>& PO<T>::OP/=(CO PO<T>& f){RE m_SZ < f.m_SZ?*TH:OP=(Quotient(*TH,f));}TE <TY T>PO<T> PO<T>::Quotient(CO PO<T>& f0,CO PO<T>& 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<T>(f0_transpose_SZ,Transpose(f1,f1_transpose_SZ))),f1.m_SZ);}TE <TY T>PO<T> PO<T>::TransposeQuotient(CO PO<T>& f0,CRUI f0_transpose_SZ,CO PO<T>& f1_transpose_inverse,CRUI f1_SZ){TRPO<T> 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<T>::m_f[d0],f0_transpose.PO<T>::m_f[ f0_transpose_SZ - 1 - d0 ]);}RE f0_transpose;}TE <TY T>PO<T> PO<T>::Transpose(CO PO<T>& f,CRUI f_transpose_SZ){VE<T> 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<T>(MO(f_transpose));}TE <TY T>PO<T>& PO<T>::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(UI i = 0;i < m_SZ;i++){m_f[i] %= t;}RE *TH;}TE <TY T>PO<T>& PO<T>::OP%=(CO PO<T>& f){if(m_SZ >= f.m_SZ){OP-=((*TH / f) * f);ReMORedundantZero();}RE *TH;}TE <TY T> IN PO<T> PO<T>::OP-() CO{RE MO(PO<T>() -= *TH);}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};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<T> 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 *= *TH;for(UI d = 0;d < m_SZ;d++){m_f[d] = exp_t_transpose.PO<T>::m_f[d + m_SZ - 1] * factorial_inv[d];}}RE *TH;}TE <TY T> IN CO VE<T>& PO<T>::GetCoefficient() CO NE{RE m_f;}TE <TY T> IN CRUI PO<T>::SZ() CO NE{RE m_SZ;}TE <TY T> IN VO PO<T>::swap(PO<T>& f){m_f.swap(f.m_f);swap(m_SZ,f.m_SZ);}TE <TY T> IN VO PO<T>::swap(VE<T>& f){m_f.swap(f);m_SZ = m_f.SZ();}TE <TY T>VO PO<T>::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 <TY T>string PO<T>::Display() CO NE{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 <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(CRUI i){ST VE<T> 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 <TY T> IN CO T& PO<T>::factorial_inverse(CRUI i){ST VE<T> 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 <TY T>bool OP==(CO PO<T>& f0,CO T& t1){CRUI SZ = f0.SZ();CO T& zero = PO<T>::CO_zero();for(UI 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){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 <TY T,TY P> IN bool OP!=(CO PO<T>& f0,CO P& f1){RE !(f0 == f1);}TE <TY T,TY P> IN PO<T> OP+(CO PO<T>& f0,CO P& f1){RE MO(PO<T>(f0) += f1);}TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f){RE PO<T>::zero() - f;}TE <TY T,TY P> IN PO<T> OP-(CO PO<T>& f0,CO P& f1){RE MO(PO<T>(f0) -= f1);}TE <TY T,TY P> IN PO<T> OP*(CO PO<T>& f0,CO P& f1){RE MO(PO<T>(f0) *= f1);}TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO T& t1){RE MO(PO<T>(f0) /= t1);}TE <TY T> IN PO<T> OP/(CO PO<T>& f0,CO PO<T>& f1){RE PO<T>::Quotient(f0,f1);}TE <TY T,TY P> IN PO<T> OP%(CO PO<T>& f0,CO P& f1){RE MO(PO<T>(f0) %= f1);}TE <TY T> PO<T> OP<<(CO PO<T>& f,CO T& t){RE MO(PO<T>(f) <<= t);};TE <TY T,TE <TY> TY V>T& Prod(V<T>& f){if(f.empty()){f.push_back(T(1));}if(f.SZ() == 1){RE f.front();}auto I = f.BE(),EN = f.EN();WH(I != EN){T& t = *I;I++;if(I != EN){t *= *I;I = f.erase(I);}}RE Prod(f);}

TE <TY T,TE <TY> TY V1,TE <TY> TY V2,TE <TY> TY V3>VO SetPointTreeEvaluation(CO PO<T>& f,CO V1<V2<PO<T> > >& point_tree,V3<T>& AN){CO V2<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() = f % prod.front();auto I_tree = point_tree.BE(),EN_tree = point_tree.EN();I_tree++;WH(I_tree != EN_tree){auto I_residue = residue.BE(),EN_residue = residue.EN();auto I_node = I_tree->BE(),EN_node = I_tree->EN();WH(I_residue != EN_residue){CO PO<T>& f = *I_node;I_node++;if(I_node != EN_node){*(residue.insert(I_residue,zero)) = *I_residue % f;*I_residue %= *I_node;I_node++;}I_residue++;}I_tree++;}for(auto I_residue = residue.BE(),EN_residue = residue.EN();I_residue != EN_residue;I_residue++){AN.push_back((*I_residue)[0]);}RE;}TE <TY T,TE <TY> TY V1,TE <TY> TY V2> IN VO SetMultipointEvaluation(CO PO<T>& f,CO V1<T>& point,V2<T>& AN){LI<LI<PO<T> > > pt{};SetPointTree(point,pt);SetPointTreeEvaluation(f,pt,AN);}TE <TY T,TE <TY> TY V1,TE <TY> TY V2 >VO SetProductTree(V1<V2<T> >& product_tree){V2<T> empty{};V2<T> *p_node = &(product_tree.back());WH(p_node->SZ() > 1){product_tree.push_front(empty);V2<T>& node_curr = product_tree.front();for(auto I = p_node->BE(),EN = p_node->EN();I != EN;I++){ST CO T null{};node_curr.push_back(null);T& f = *I;I++;if(I == EN){node_curr.back() = f;break;}else{node_curr.back() = f * *I;}}p_node = &node_curr;}RE;}TE <TY T,TE <TY> TY V1,TE <TY> TY V2,TE <TY> TY V3>VO SetPointTree(CO V1<T>& point,V2<V3<PO<T> > >& point_tree){ST CO V3<PO<T> > empty{};point_tree.push_front(empty);V3<PO<T> >& linear = point_tree.front();for(auto I = point.BE(),EN = point.EN();I != EN;I++){ST CO PO<T> x{1,PO<T>::CO_one()};linear.push_back(x);linear.back()[0] -= *I;}SetProductTree(point_tree);RE;}

#define SET_MA_MULTIPOINT_EVALUATION(SAMPLE_NUM_MAX,FINAL_LE,POINT) point = VE<T>(SAMPLE_NUM_MAX + 1);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){point[t] = POINT;}LI<LI<PO<T> > > pt{};SetPointTree(point,pt);VE<T> eval[Y][Y] ={};for(UI y = 0;y < Y;y++){CO VE<PO<T> >& M_ref_y = M_ref[y];VE<T> (&eval_y)[Y] = eval[y];for(UI x = 0;x < Y;x++){SetPointTreeEvaluation(M_ref_y[x],pt,eval_y[x]);}}VE<MA<Y,Y,T> > sample(SAMPLE_NUM_MAX + 1,MA<Y,Y,T>::Zero());sample.reserve(FINAL_LE);for(UI t = 0;t <= SAMPLE_NUM_MAX;t++){VE<VE<T> >& sample_t_ref = sample[t].RefTable();for(UI y = 0;y < Y;y++){VE<T>& sample_t_ref_y = sample_t_ref[y];VE<T> (&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_LE) VE<MA<Y,Y,T> > eval_odd{};VE<MA<Y,Y,T> > eval_even{};SetIntervalEvaluation(subinterval_num_max,subinterval_LE / interval_LE,REST_INTERVAL_LE + subinterval_num_max + 1,sample,eval_odd);SetIntervalEvaluation(subinterval_num_max,T(subinterval_num_max + 1),REST_INTERVAL_LE,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_LE;t++){sample.push_back(eval_odd[t + subinterval_num_max + 1] * eval_even[t]);}
TE <TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI LE,VE<T>& eval){for(UI d = 0;d <= deg;d++){eval[d] *= PO<T>::factorial_inverse(d);}VE<T> v{};v.swap(eval);TRPO<T> f{deg + 1,MO(v)};ST PO<T> exp_inv{};for(UI 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.ReMORedundantZero();UI deg_f = f.SZ();if(deg_f == 0){eval = VE<T>(LE,PO<T>::CO_zero());RE;}f.SetTruncation(deg_f);deg_f--;for(UI d = 0;d <= deg_f;d++){f[d] *= PO<T>::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<T> exp_t_Mahler{};T t_Mahler = PO<T>::CO_one();for(UI 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(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<T>::factorial_inverse(d);}f.SetTruncation(LE);ST PO<T> exp{};for(UI d = exp.SZ();d < LE;d++){exp[d] = PO<T>::factorial_inverse(d);}f *= exp;for(UI d = 0;d < LE;d++){f[d] *= PO<T>::factorial(d);}f.swap(eval);RE;}TE <UI Y,UI X,TY T>VO SetIntervalEvaluation(CRUI deg,CO T& t_start,CRUI LE,CO VE<MA<Y,X,T> >& sample,VE<MA<Y,X,T> >& eval){eval = VE<MA<Y,X,T> >(LE,MA<Y,X,T>::Zero());VE<T> sample_copy[Y][X] ={};for(UI t = 0;t <= deg;t++){CO VE<VE<T> >& table = sample[t].GetTable();for(UI y = 0;y < Y;y++){VE<T> (&sample_copy_y)[X] = sample_copy[y];CO VE<T>& 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<T> (&sample_copy_y)[X] = sample_copy[y];for(UI x = 0;x < X;x++){VE<T>& sample_copy_yx = sample_copy_y[x];SetIntervalEvaluation(deg,t_start,LE,sample_copy_yx);for(UI i = 0;i < LE;i++){VE<VE<T> >& table = eval[i].RefTable();table[y][x] = sample_copy_yx[i];}}}RE;}TE <UI Y,TY T>VO SetPRecursiveMAAction(CO MA<Y,Y,PO<T> >& M,MA<Y,1,T>& v,CRUI LE){if(LE == 0){RE;}CO VE<VE<PO<T> > >& M_ref = M.GetTable();UI deg = 1;for(UI y = 0;y < Y;y++){CO VE<PO<T>>& 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_LE = 1;int EX = 0;WH(interval_LE * (interval_LE * deg + 1) <= LE){interval_LE *= 2;EX++;}interval_LE /= 2;EX--;UI interval_num_max;UI t_rest_start;VE<T> point{};if(EX > 0){CO UI interval_num_lim = LE / interval_LE;interval_num_max = interval_num_lim - 1;t_rest_start = interval_LE * interval_num_lim;UI subinterval_num_max = deg;T subinterval_LE = PO<T>::CO_one();SET_MA_MULTIPOINT_EVALUATION(subinterval_num_max,interval_num_lim,t * interval_LE);for(int e = 1;e < EX;e++){MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(subinterval_num_max);subinterval_num_max *= 2;subinterval_LE *= 2;}UI rest_interval_LE = interval_num_max - subinterval_num_max;MULTIPLY_SUBPRODUCT_OF_PRECURSIVE_MA(rest_interval_LE);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 < LE){CO UI rest_num_lim = LE - 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<MP>;CL D{PU:TTMA<MPX> m_M;MPX m_pt;IN D() : m_M(),m_pt() {};IN D(TTMA<MPX>&& 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<list<D> > d_prod{};list<list<int> > over_M{};d_prod.push_front(list<D>());over_M.push_front(list<int>());list<D>& d_prod_init = d_prod.front();list<int>& 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<MPX>{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<MPX>(1),X - Qt.m_N));over_M_init.push_front(0);k_start = Qt.m_K;}SetProductTree(d_prod);SetProductTree(over_M);list<MA<2,1,MPX> > 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;}