#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 uint&
US namespace std;US uint = unsigned int;US ull = unsigned long long;
#define MAIN __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi,bmi2" ) ) ) int main
#define TYPE_OF(VAR) decay_t<decltype(VAR)>
#define UNTIE ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define CEXPR(LL,BOUND,VALUE) CE 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"
CEXPR(uint,P,998244353);TE <uint M,TY INT> CE INT& RS(INT& n)NE{RE n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n %= M;}TE <uint M> CE uint& RS(uint& n)NE{RE n %= M;}TE <uint M> CE ull& RS(ull& n)NE{RE n %= M;}TE <TY INT> CE INT& RSP(INT& n)NE{CE uint trunc = (1 << 23)- 1;INT n_u = n >> 23;n &= trunc;INT n_uq = (n_u / 7)/ 17;n_u -= n_uq * 119;n += n_u << 23;RE n < n_uq?n += P - n_uq:n -= n_uq;}TE <> CE ull& RS<P,ull>(ull& n)NE{CE ull Pull = P;CE ull Pull2 = (Pull - 1)* (Pull - 1);RE RSP(n > Pull2?n -= Pull2:n);}TE <uint M,TY INT> CE INT RS(INT&& n)NE{RE MO(RS<M>(n));}TE <uint M,TY INT> CE INT RS(CO INT& n)NE{RE RS<M>(INT(n));}
#define SFINAE_FOR_MOD(DEFAULT)TY T,enable_if_t<is_constructible<uint,decay_t<T> >::value>* DEFAULT
#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 <SFINAE_FOR_MOD(= nullptr)> IN Mod<M> OP FUNC(T&& n)CO NE;
#define DF_OF_CM_FOR_MOD(FUNC)TE <uint 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 <uint M> IN Mod<M> Mod<M>::OP FUNC(CO Mod<M>& n)CO NE{RE MO(Mod<M>(*TH)FUNC ## = n);}TE <uint M> TE <SFINAE_FOR_MOD()> IN Mod<M> Mod<M>::OP FUNC(T&& n)CO NE{RE FORMULA;}TE <uint M,SFINAE_FOR_MOD(= nullptr)> IN Mod<M> OP FUNC(T&& n0,CO Mod<M>& n1)NE{RE MO(Mod<M>(forward<T>(n0))FUNC ## = n1);}
TE <uint M>CL Mod{PU:uint m_n;PU:CE Mod()NE;CE Mod(CO Mod<M>& n)NE;CE Mod(Mod<M>& n)NE;CE Mod(Mod<M>&& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> CE Mod(CO T& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> CE Mod(T& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> CE Mod(T&& n)NE;CE Mod<M>& OP=(CO Mod<M>& n)NE;CE Mod<M>& OP=(Mod<M>&& n)NE;CE Mod<M>& OP+=(CO Mod<M>& n)NE;CE Mod<M>& OP-=(CO Mod<M>& n)NE;CE Mod<M>& OP*=(CO Mod<M>& n)NE;IN Mod<M>& OP/=(CO Mod<M>& n);CE Mod<M>& OP<<=(int n)NE;CE Mod<M>& OP>>=(int n)NE;CE Mod<M>& OP++()NE;CE Mod<M> OP++(int)NE;CE Mod<M>& OP--()NE;CE 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(/);CE Mod<M> OP<<(int n)CO NE;CE Mod<M> OP>>(int n)CO NE;CE Mod<M> OP-()CO NE;CE Mod<M>& SignInvert()NE;CE Mod<M>& Double()NE;CE Mod<M>& Halve()NE;IN Mod<M>& Invert();TE <TY T> CE Mod<M>& PositivePW(T&& EX)NE;TE <TY T> CE Mod<M>& NonNegativePW(T&& EX)NE;TE <TY T> CE Mod<M>& PW(T&& EX);CE VO swap(Mod<M>& n)NE;CE CO uint& RP()CO NE;ST CE Mod<M> DeRP(CO uint& n)NE;ST CE uint& Normalise(uint& n)NE;ST IN CO Mod<M>& Inverse(CO uint& n)NE;ST IN CO Mod<M>& Factorial(CO uint& n)NE;ST IN CO Mod<M>& FactorialInverse(CO uint& n)NE;ST IN CO Mod<M>& zero()NE;ST IN CO Mod<M>& one()NE;PU:TE <TY T> CE Mod<M>& Ref(T&& n)NE;};
#define SFINAE_FOR_MN(DEFAULT)TY T,enable_if_t<is_constructible<Mod<M>,decay_t<T> >::value>* DEFAULT
#define DC_OF_AR_FOR_MN(FUNC)IN MN<M> OP FUNC(CO MN<M>& n)CO NE;TE <SFINAE_FOR_MOD(= nullptr)> IN MN<M> OP FUNC(T&& n)CO NE;
#define DF_OF_CM_FOR_MN(FUNC)TE <uint M> IN bool MN<M>::OP FUNC(CO MN<M>& n)CO NE{RE m_n FUNC n.m_n;}
#define DF_OF_AR_FOR_MN(FUNC,FORMULA)TE <uint M> IN MN<M> MN<M>::OP FUNC(CO MN<M>& n)CO NE{RE MO(MN<M>(*TH)FUNC ## = n);}TE <uint M> TE <SFINAE_FOR_MOD()> IN MN<M> MN<M>::OP FUNC(T&& n)CO NE{RE FORMULA;}TE <uint M,SFINAE_FOR_MOD(= nullptr)> IN MN<M> OP FUNC(T&& n0,CO MN<M>& n1)NE{RE MO(MN<M>(forward<T>(n0))FUNC ## = n1);}
TE <uint M>CL MN :PU Mod<M>{PU:CE MN()NE;CE MN(CO MN<M>& n)NE;CE MN(MN<M>& n)NE;CE MN(MN<M>&& n)NE;TE <SFINAE_FOR_MN(= nullptr)> CE MN(CO T& n)NE;TE <SFINAE_FOR_MN(= nullptr)> CE MN(T&& n)NE;CE MN<M>& OP=(CO MN<M>& n)NE;CE MN<M>& OP=(MN<M>&& n)NE;CE MN<M>& OP+=(CO MN<M>& n)NE;CE MN<M>& OP-=(CO MN<M>& n)NE;CE MN<M>& OP*=(CO MN<M>& n)NE;IN MN<M>& OP/=(CO MN<M>& n);CE MN<M>& OP<<=(int n)NE;CE MN<M>& OP>>=(int n)NE;CE MN<M>& OP++()NE;CE MN<M> OP++(int)NE;CE MN<M>& OP--()NE;CE MN<M> OP--(int)NE;DC_OF_AR_FOR_MN(+);DC_OF_AR_FOR_MN(-);DC_OF_AR_FOR_MN(*);DC_OF_AR_FOR_MN(/);CE MN<M> OP<<(int n)CO NE;CE MN<M> OP>>(int n)CO NE;CE MN<M> OP-()CO NE;CE MN<M>& SignInvert()NE;CE MN<M>& Double()NE;CE MN<M>& Halve()NE;CE MN<M>& Invert();TE <TY T> CE MN<M>& PositivePW(T&& EX)NE;TE <TY T> CE MN<M>& NonNegativePW(T&& EX)NE;TE <TY T> CE MN<M>& PW(T&& EX);CE uint RP()CO NE;CE Mod<M> Reduce()CO NE;ST CE MN<M> DeRP(CO uint& n)NE;ST IN CO MN<M>& Formise(CO uint& n)NE;ST IN CO MN<M>& Inverse(CO uint& n)NE;ST IN CO MN<M>& Factorial(CO uint& n)NE;ST IN CO MN<M>& FactorialInverse(CO uint& n)NE;ST IN CO MN<M>& zero()NE;ST IN CO MN<M>& one()NE;PU:ST CE uint Form(CO uint& n)NE;ST CE ull& Reduction(ull& n)NE;ST CE ull& ReducedMU(ull& n,CO uint& m)NE;ST CE uint MU(CO uint& n0,CO uint& n1)NE;ST CE uint BaseSquareTruncation(uint& n)NE;TE <TY T> CE MN<M>& Ref(T&& n)NE;};TE <uint M> CE MN<M> Twice(CO MN<M>& n)NE;TE <uint M> CE MN<M> Half(CO MN<M>& n)NE;TE <uint M> CE MN<M> Inverse(CO MN<M>& n);TE <uint M,TY T> CE MN<M> PW(CO MN<M>& n,CO T& EX);TE <TY T> CE MN<2> PW(CO MN<2>& n,CO T& p);TE <TY T> CE T Square(CO T& t);TE <> CE MN<2> Square<MN<2> >(CO MN<2>& t);TE <uint M> CE VO swap(MN<M>& n0,MN<M>& n1)NE;TE <uint M> IN string to_string(CO MN<M>& n)NE;TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO MN<M>& n);
TE <uint M>CL COantsForMod{PU:COantsForMod()= delete;ST CE bool g_even = ((M & 1)== 0);ST CE uint g_memory_bound = 1000000;ST CE uint g_memory_LE = M < g_memory_bound?M:g_memory_bound;ST CE ull MNBasePW(ull&& EX)NE;ST CE uint g_M_minus = M - 1;ST CE uint g_M_minus_2 = M - 2;ST CE uint g_M_minus_2_neg = 2 - M;ST CE int g_MN_digit = 32;ST CE ull g_MN_base = ull(1)<< g_MN_digit;ST CE uint g_MN_base_minus = uint(g_MN_base - 1);ST CE uint g_MN_digit_half = (g_MN_digit + 1)>> 1;ST CE uint g_MN_base_sqrt_minus = (1 << g_MN_digit_half)- 1;ST CE uint g_MN_M_neg_inverse = uint((g_MN_base - MNBasePW((ull(1)<< (g_MN_digit - 1))- 1))& g_MN_base_minus);ST CE uint g_MN_base_mod = uint(g_MN_base % M);ST CE uint g_MN_base_square_mod = uint(((g_MN_base % M)* (g_MN_base % M))% M);};TE <uint M> CE ull COantsForMod<M>::MNBasePW(ull&& EX)NE{ull prod = 1;ull PW = M;WH(EX != 0){(EX & 1)== 1?(prod *= PW)&= g_MN_base_minus:prod;EX >>= 1;(PW *= PW)&= g_MN_base_minus;}RE prod;}
#include <immintrin.h>
#define SET_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR0,SCALAR1,SCALAR2,SCALAR3)CE UINT VE_NAME ## _copy[4] ={SCALAR0,SCALAR1,SCALAR2,SCALAR3};ST CO __m128i v_ ## VE_NAME = _mm_load_si128((__m128i*)VE_NAME ##_copy);
#define SET_VE_64_128_FOR_SIMD(UINT,VE_NAME,SCALAR0,SCALAR1)CE UINT VE_NAME ## _copy[2] ={SCALAR0,SCALAR1};ST CO __m128i v_ ## VE_NAME = _mm_load_si128((__m128i*)VE_NAME ##_copy);
#define SET_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR0,SCALAR1,SCALAR2,SCALAR3)CE ULL VE_NAME ## _copy[4] ={SCALAR0,SCALAR1,SCALAR2,SCALAR3};ST CO __m256i v_ ## VE_NAME = _mm256_load_si256((__m256i*)VE_NAME ##_copy);
#define SET_CO_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR)SET_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR,SCALAR,SCALAR,SCALAR);
#define SET_CO_VE_64_128_FOR_SIMD(ULL,VE_NAME,SCALAR)SET_VE_64_128_FOR_SIMD(ULL,VE_NAME,SCALAR,SCALAR);
#define SET_CO_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR)SET_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR,SCALAR,SCALAR,SCALAR);
TE <uint M>CL COantsForSIMDForMod{PU:COantsForSIMDForMod()= delete;ST IN CO __m128i& v_M()NE;ST IN CO __m128i& v_Mull()NE;ST IN CO __m128i& v_M_minus()NE;ST IN CO __m128i& v_M_neg_inverse()NE;ST IN CO __m128i& v_digitull()NE;};TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M,M);RE v_M;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_Mull()NE{SET_CO_VE_64_128_FOR_SIMD(ull,Mull,M);RE v_Mull;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M_minus()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M_minus,M - 1);RE v_M_minus;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M_neg_inverse()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M_neg_inverse,COantsForMod<M>::g_MN_M_neg_inverse);RE v_M_neg_inverse;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_digitull()NE{SET_CO_VE_64_128_FOR_SIMD(ull,digitull,COantsForMod<M>::g_MN_digit);RE v_digitull;}TE <uint M> IN __m128i& SIMD_RS_32_128(__m128i& v)NE{CO __m128i& v_M = COantsForSIMDForMod<M>::v_M();RE v -= v_M * _mm_cmpgt_epi32(v,v_M);}TE <uint M> IN __m128i& SIMD_RS_64_128(__m128i& v)NE{ull v_copy[2];_mm_store_si128((__m128i*)v_copy,v);for(uint i = 0;i < 2;i++){ull& v_copy_i = v_copy[i];v_copy_i = (v_copy_i < M?0:M);}RE v -= _mm_load_si128((__m128i*)v_copy);}TE <uint M> IN __m256i& SIMD_RS_64_256(__m256i& v)NE{ull v_copy[4];_mm256_store_si256((__m256i*)v_copy,v);for(uint i = 0;i < 4;i++){ull& v_copy_i = v_copy[i];v_copy_i = (v_copy_i < M?0:M);}RE v -= _mm256_load_si256((__m256i*)v_copy);}CE int SIMD_Shuffle(CRI a0,CRI a1,CRI a2,CRI a3)NE{RE (a0 << (0 << 1))+ (a1 << (1 << 1))+ (a2 << (2 << 1))+ (a3 << (3 << 1));}TE <uint M> IN VO SIMD_Addition_32_64(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& b0,CO Mod<M>& b1,Mod<M>& c0,Mod<M>& c1)NE{uint a_copy[4] ={a0.m_n,a1.m_n,0,0};uint b_copy[4] ={b0.m_n,b1.m_n,0,0};__m128i v_a = _mm_load_si128((__m128i*)a_copy);v_a += _mm_load_si128((__m128i*)b_copy);ST CO __m128i& v_M_minus = COantsForSIMDForMod<M>::v_M_minus();ST CO __m128i& v_M = COantsForSIMDForMod<M>::v_M();v_a += _mm_cmpgt_epi32(v_a,v_M_minus)& v_M;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);RE;}TE <uint M> IN VO SIMD_Addition_32_128(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& a2,CO Mod<M>& a3,CO Mod<M>& b0,CO Mod<M>& b1,CO Mod<M>& b2,CO Mod<M>& b3,Mod<M>& c0,Mod<M>& c1,Mod<M>& c2,Mod<M>& c3)NE{uint a_copy[4] ={a0.m_n,a1.m_n,a2.m_n,a3.m_n};uint b_copy[4] ={b0.m_n,b1.m_n,b2.m_n,b3.m_n};__m128i v_a = _mm_load_si128((__m128i*)a_copy)+ _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 4;i++){b_copy[i] = a_copy[i] < M?0:M;}v_a -= _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);c2.m_n = MO(a_copy[2]);c3.m_n = MO(a_copy[3]);RE;}TE <uint M> IN VO SIMD_Substracition_32_64(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& b0,CO Mod<M>& b1,Mod<M>& c0,Mod<M>& c1)NE{uint a_copy[4] ={a0.m_n,a1.m_n,0,0};uint b_copy[4] ={b0.m_n,b1.m_n,0,0};__m128i v_a = _mm_load_si128((__m128i*)a_copy);__m128i v_b = _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 2;i++){b_copy[i] = a_copy[i] < b_copy[i]?M:0;}(v_a += _mm_load_si128((__m128i*)b_copy))-= v_b;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);RE;}TE <uint M> IN VO SIMD_Subtraction_32_128(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& a2,CO Mod<M>& a3,CO Mod<M>& b0,CO Mod<M>& b1,CO Mod<M>& b2,CO Mod<M>& b3,Mod<M>& c0,Mod<M>& c1,Mod<M>& c2,Mod<M>& c3)NE{uint a_copy[4] ={a0.m_n,a1.m_n,a2.m_n,a3.m_n};uint b_copy[4] ={b0.m_n,b1.m_n,b2.m_n,b3.m_n};__m128i v_a = _mm_load_si128((__m128i*)a_copy);__m128i v_b = _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 4;i++){b_copy[i] = a_copy[i] < b_copy[i]?M:0;}(v_a += _mm_load_si128((__m128i*)b_copy))-= v_b;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);c2.m_n = MO(a_copy[2]);c3.m_n = MO(a_copy[3]);RE;}
US MP = Mod<P>;US MNP = MN<P>;TE <uint M> CE uint MN<M>::Form(CO uint& n)NE{ull n_copy = n;RE uint(MO(Reduction(n_copy *= COantsForMod<M>::g_MN_base_square_mod)));}TE <uint M> CE ull& MN<M>::Reduction(ull& n)NE{ull n_sub = n & COantsForMod<M>::g_MN_base_minus;RE ((n += ((n_sub *= COantsForMod<M>::g_MN_M_neg_inverse)&= COantsForMod<M>::g_MN_base_minus)*= M)>>= COantsForMod<M>::g_MN_digit)< M?n:n -= M;}TE <uint M> CE ull& MN<M>::ReducedMU(ull& n,CO uint& m)NE{RE Reduction(n *= m);}TE <uint M> CE uint MN<M>::MU(CO uint& n0,CO uint& n1)NE{ull n0_copy = n0;RE uint(MO(ReducedMU(ReducedMU(n0_copy,n1),COantsForMod<M>::g_MN_base_square_mod)));}TE <uint M> CE uint MN<M>::BaseSquareTruncation(uint& n)NE{CO uint n_u = n >> COantsForMod<M>::g_MN_digit_half;n &= COantsForMod<M>::g_MN_base_sqrt_minus;RE n_u;}TE <uint M> CE MN<M>::MN()NE:Mod<M>(){static_assert(! COantsForMod<M>::g_even);}TE <uint M> CE MN<M>::MN(CO MN<M>& n)NE:Mod<M>(n){}TE <uint M> CE MN<M>::MN(MN<M>& n)NE:Mod<M>(n){}TE <uint M> CE MN<M>::MN(MN<M>&& n)NE:Mod<M>(MO(n)){}TE <uint M> TE <SFINAE_FOR_MN()> CE MN<M>::MN(CO T& n)NE:Mod<M>(n){static_assert(! COantsForMod<M>::g_even);Mod<M>::m_n = Form(Mod<M>::m_n);}TE <uint M> TE <SFINAE_FOR_MN()> CE MN<M>::MN(T&& n)NE:Mod<M>(forward<T>(n)){static_assert(! COantsForMod<M>::g_even);Mod<M>::m_n = Form(Mod<M>::m_n);}TE <uint M> CE MN<M>& MN<M>::OP=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP=(n));}TE <uint M> CE MN<M>& MN<M>::OP=(MN<M>&& n)NE{RE Ref(Mod<M>::OP=(MO(n)));}TE <uint M> CE MN<M>& MN<M>::OP+=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP+=(n));}TE <uint M> CE MN<M>& MN<M>::OP-=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP-=(n));}TE <uint M> CE MN<M>& MN<M>::OP*=(CO MN<M>& n)NE{ull m_n_copy = Mod<M>::m_n;RE Ref(Mod<M>::m_n = MO(ReducedMU(m_n_copy,n.m_n)));}TE <uint M> IN MN<M>& MN<M>::OP/=(CO MN<M>& n){RE OP*=(MN<M>(n).Invert());}TE <uint M> CE MN<M>& MN<M>::OP<<=(int n)NE{RE Ref(Mod<M>::OP<<=(n));}TE <uint M> CE MN<M>& MN<M>::OP>>=(int n)NE{RE Ref(Mod<M>::OP>>=(n));}TE <uint M> CE MN<M>& MN<M>::OP++()NE{RE Ref(Mod<M>::Normalise(Mod<M>::m_n += COantsForMod<M>::g_MN_base_mod));}TE <uint M> CE MN<M> MN<M>::OP++(int)NE{MN<M> n{*TH};OP++();RE n;}TE <uint M> CE MN<M>& MN<M>::OP--()NE{RE Ref(Mod<M>::m_n < COantsForMod<M>::g_MN_base_mod?((Mod<M>::m_n += M)-= COantsForMod<M>::g_MN_base_mod):Mod<M>::m_n -= COantsForMod<M>::g_MN_base_mod);}TE <uint M> CE MN<M> MN<M>::OP--(int)NE{MN<M> n{*TH};OP--();RE n;}DF_OF_AR_FOR_MN(+,MN<M>(forward<T>(n))+= *TH);DF_OF_AR_FOR_MN(-,MN<M>(forward<T>(n)).SignInvert()+= *TH);DF_OF_AR_FOR_MN(*,MN<M>(forward<T>(n))*= *TH);DF_OF_AR_FOR_MN(/,MN<M>(forward<T>(n)).Invert()*= *TH);TE <uint M> CE MN<M> MN<M>::OP<<(int n)CO NE{RE MO(MN<M>(*TH)<<= n);}TE <uint M> CE MN<M> MN<M>::OP>>(int n)CO NE{RE MO(MN<M>(*TH)>>= n);}TE <uint M> CE MN<M> MN<M>::OP-()CO NE{RE MO(MN<M>(*TH).SignInvert());}TE <uint M> CE MN<M>& MN<M>::SignInvert()NE{RE Ref(Mod<M>::m_n > 0?Mod<M>::m_n = M - Mod<M>::m_n:Mod<M>::m_n);}TE <uint M> CE MN<M>& MN<M>::Double()NE{RE Ref(Mod<M>::Double());}TE <uint M> CE MN<M>& MN<M>::Halve()NE{RE Ref(Mod<M>::Halve());}TE <uint M> CE MN<M>& MN<M>::Invert(){assert(Mod<M>::m_n > 0);RE PositivePW(uint(COantsForMod<M>::g_M_minus_2));}TE <uint M> TE <TY T> CE MN<M>& MN<M>::PositivePW(T&& EX)NE{MN<M> PW{*TH};(--EX)%= COantsForMod<M>::g_M_minus_2;WH(EX != 0){(EX & 1)== 1?OP*=(PW):*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <uint M> TE <TY T> CE MN<M>& MN<M>::NonNegativePW(T&& EX)NE{RE EX == 0?Ref(Mod<M>::m_n = 1):PositivePW(forward<T>(EX));}TE <uint M> TE <TY T> CE MN<M>& MN<M>::PW(T&& EX){bool neg = EX < 0;assert(!(neg && Mod<M>::m_n == 0));RE neg?PositivePW(forward<T>(EX *= COantsForMod<M>::g_M_minus_2_neg)):NonNegativePW(forward<T>(EX));}TE <uint M> CE uint MN<M>::RP()CO NE{ull m_n_copy = Mod<M>::m_n;RE MO(Reduction(m_n_copy));}TE <uint M> CE Mod<M> MN<M>::Reduce()CO NE{ull m_n_copy = Mod<M>::m_n;RE Mod<M>::DeRP(MO(Reduction(m_n_copy)));}TE <uint M> CE MN<M> MN<M>::DeRP(CO uint& n)NE{RE MN<M>(Mod<M>::DeRP(n));}TE <uint M> IN CO MN<M>& MN<M>::Formise(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = DeRP(LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::Inverse(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>(Mod<M>::Inverse(LE_curr));LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::Factorial(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;ST MN<M> val_curr{one()};MN<M> val_last{one()};WH(LE_curr <= n){memory[LE_curr++] = val_curr *= ++val_last;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::FactorialInverse(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;ST MN<M> val_curr{one()};MN<M> val_last{one()};WH(LE_curr <= n){memory[LE_curr] = val_curr *= Inverse(LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::zero()NE{ST CE MN<M> z{};RE z;}TE <uint M> IN CO MN<M>& MN<M>::one()NE{ST CE MN<M> o{DeRP(1)};RE o;}TE <uint M> TE <TY T> CE MN<M>& MN<M>::Ref(T&& n)NE{RE *TH;}TE <uint M> CE MN<M> Twice(CO MN<M>& n)NE{RE MO(MN<M>(n).Double());}TE <uint M> CE MN<M> Half(CO MN<M>& n)NE{RE MO(MN<M>(n).Halve());}TE <uint M> CE MN<M> Inverse(CO MN<M>& n){RE MO(MN<M>(n).Invert());}TE <uint M,TY T> CE MN<M> PW(CO MN<M>& n,CO T& EX){RE MO(MN<M>(n).PW(T(EX)));}TE <uint M> CE VO swap(MN<M>& n0,MN<M>& n1)NE{n0.swap(n1);}TE <uint M> IN string to_string(CO MN<M>& n)NE{RE to_string(n.RP())+ " + MZ";}TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO MN<M>& n){RE os << n.RP();}
TE <uint M> CE Mod<M>::Mod()NE:m_n(){}TE <uint M> CE Mod<M>::Mod(CO Mod<M>& n)NE:m_n(n.m_n){}TE <uint M> CE Mod<M>::Mod(Mod<M>& n)NE:m_n(n.m_n){}TE <uint M> CE Mod<M>::Mod(Mod<M>&& n)NE:m_n(MO(n.m_n)){}TE <uint M> TE <SFINAE_FOR_MOD()> CE Mod<M>::Mod(CO T& n)NE:m_n(RS<M>(n)){}TE <uint M> TE <SFINAE_FOR_MOD()> CE Mod<M>::Mod(T& n)NE:m_n(RS<M>(decay_t<T>(n))){}TE <uint M> TE <SFINAE_FOR_MOD()> CE Mod<M>::Mod(T&& n)NE:m_n(RS<M>(forward<T>(n))){}TE <uint M> CE Mod<M>& Mod<M>::OP=(CO Mod<M>& n)NE{RE Ref(m_n = n.m_n);}TE <uint M> CE Mod<M>& Mod<M>::OP=(Mod<M>&& n)NE{RE Ref(m_n = MO(n.m_n));}TE <uint M> CE Mod<M>& Mod<M>::OP+=(CO Mod<M>& n)NE{RE Ref(Normalise(m_n += n.m_n));}TE <uint M> CE Mod<M>& Mod<M>::OP-=(CO Mod<M>& n)NE{RE Ref(m_n < n.m_n?(m_n += M)-= n.m_n:m_n -= n.m_n);}TE <uint M> CE Mod<M>& Mod<M>::OP*=(CO Mod<M>& n)NE{RE Ref(m_n = COantsForMod<M>::g_even?RS<M>(ull(m_n)* n.m_n):MN<M>::MU(m_n,n.m_n));}TE <> CE MP& MP::OP*=(CO MP& n)NE{ull m_n_copy = m_n;RE Ref(m_n = MO((m_n_copy *= n.m_n)< P?m_n_copy:RSP(m_n_copy)));}TE <uint M> IN Mod<M>& Mod<M>::OP/=(CO Mod<M>& n){RE OP*=(Mod<M>(n).Invert());}TE <uint M> CE Mod<M>& Mod<M>::OP<<=(int n)NE{WH(n-- > 0){Normalise(m_n <<= 1);}RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::OP>>=(int n)NE{WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += M)>>= 1;}RE *TH;}TE <uint M> CE Mod<M>& Mod<M>::OP++()NE{RE Ref(m_n < COantsForMod<M>::g_M_minus?++m_n:m_n = 0);}TE <uint M> CE Mod<M> Mod<M>::OP++(int)NE{Mod<M> n{*TH};OP++();RE n;}TE <uint M> CE Mod<M>& Mod<M>::OP--()NE{RE Ref(m_n == 0?m_n = COantsForMod<M>::g_M_minus:--m_n);}TE <uint M> CE 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 <uint M> CE Mod<M> Mod<M>::OP<<(int n)CO NE{RE MO(Mod<M>(*TH)<<= n);}TE <uint M> CE Mod<M> Mod<M>::OP>>(int n)CO NE{RE MO(Mod<M>(*TH)>>= n);}TE <uint M> CE Mod<M> Mod<M>::OP-()CO NE{RE MO(Mod<M>(*TH).SignInvert());}TE <uint M> CE Mod<M>& Mod<M>::SignInvert()NE{RE Ref(m_n > 0?m_n = M - m_n:m_n);}TE <uint M> CE Mod<M>& Mod<M>::Double()NE{RE Ref(Normalise(m_n <<= 1));}TE <uint M> CE Mod<M>& Mod<M>::Halve()NE{RE Ref(((m_n & 1)== 0?m_n:m_n += M)>>= 1);}TE <uint M> IN Mod<M>& Mod<M>::Invert(){assert(m_n > 0);uint m_n_neg;RE m_n < COantsForMod<M>::g_memory_LE?Ref(m_n = Inverse(m_n).m_n):(m_n_neg = M - m_n < COantsForMod<M>::g_memory_LE)?Ref(m_n = M - Inverse(m_n_neg).m_n):PositivePW(uint(COantsForMod<M>::g_M_minus_2));}TE <> IN Mod<2>& Mod<2>::Invert(){assert(m_n > 0);RE *TH;}TE <uint M> TE <TY T> CE Mod<M>& Mod<M>::PositivePW(T&& EX)NE{Mod<M> PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?OP*=(PW):*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <> TE <TY T> CE Mod<2>& Mod<2>::PositivePW(T&& EX)NE{RE *TH;}TE <uint M> TE <TY T> CE Mod<M>& Mod<M>::NonNegativePW(T&& EX)NE{RE EX == 0?Ref(m_n = 1):Ref(PositivePW(forward<T>(EX)));}TE <uint M> TE <TY T> CE Mod<M>& Mod<M>::PW(T&& EX){bool neg = EX < 0;assert(!(neg && m_n == 0));neg?EX *= COantsForMod<M>::g_M_minus_2_neg:EX;RE m_n == 0?*TH:(EX %= COantsForMod<M>::g_M_minus)== 0?Ref(m_n = 1):PositivePW(forward<T>(EX));}TE <uint M> IN CO Mod<M>& Mod<M>::Inverse(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr].m_n = M - MN<M>::MU(memory[M % LE_curr].m_n,M / LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::Factorial(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>::Factorial(LE_curr).Reduce();LE_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::FactorialInverse(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>::FactorialInverse(LE_curr).Reduce();LE_curr++;}RE memory[n];}TE <uint M> CE VO Mod<M>::swap(Mod<M>& n)NE{std::swap(m_n,n.m_n);}TE <uint M> CE CO uint& Mod<M>::RP()CO NE{RE m_n;}TE <uint M> CE Mod<M> Mod<M>::DeRP(CO uint& n)NE{Mod<M> n_copy{};n_copy.m_n = n;RE n_copy;}TE <uint M> CE uint& Mod<M>::Normalise(uint& n)NE{RE n < M?n:n -= M;}TE <uint M> IN CO Mod<M>& Mod<M>::zero()NE{ST CE Mod<M> z{};RE z;}TE <uint M> IN CO Mod<M>& Mod<M>::one()NE{ST CE Mod<M> o{DeRP(1)};RE o;}TE <uint M> TE <TY T> CE Mod<M>& Mod<M>::Ref(T&& n)NE{RE *TH;}TE <uint M> CE Mod<M> Twice(CO Mod<M>& n)NE{RE MO(Mod<M>(n).Double());}TE <uint M> CE Mod<M> Half(CO Mod<M>& n)NE{RE MO(Mod<M>(n).Halve());}TE <uint M> IN Mod<M> Inverse(CO Mod<M>& n){RE MO(Mod<M>(n).Invert());}TE <uint M> CE Mod<M> Inverse_COrexpr(CO uint& n)NE{RE MO(Mod<M>::DeRP(RS<M>(n)).NonNegativePW(M - 2));}TE <uint M,TY T> CE Mod<M> PW(CO Mod<M>& n,CO T& EX){RE MO(Mod<M>(n).PW(T(EX)));}TE <uint M> CE VO swap(Mod<M>& n0,Mod<M>& n1)NE{n0.swap(n1);}TE <uint M> IN string to_string(CO Mod<M>& n)NE{RE to_string(n.RP())+ " + MZ";}TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n){RE os << n.RP();}
#define SFINAE_FOR_MA(DEFAULT) TY Arg,enable_if_t<is_constructible<T,Arg>::value>* DEFAULT
#define VEISATION_FOR_TTMA_FOR_MOD(MODULO) TE <> IN TTMA<Mod<MODULO> >& TTMA<Mod<MODULO> >::OP+=(CO TTMA<Mod<MODULO> >& mat) NE{SIMD_Addition_32_128(m_M00,m_M01,m_M10,m_M11,mat.m_M00,mat.m_M01,mat.m_M10,mat.m_M11,m_M00,m_M01,m_M10,m_M11);RE *TH;}TE <> IN TTMA<MN<MODULO> >& TTMA<MN<MODULO> >::OP+=(CO TTMA<MN<MODULO> >& mat) NE{SIMD_Addition_32_128(m_M00,m_M01,m_M10,m_M11,mat.m_M00,mat.m_M01,mat.m_M10,mat.m_M11,m_M00,m_M01,m_M10,m_M11);RE *TH;}TE <> IN TTMA<Mod<MODULO> >& TTMA<Mod<MODULO> >::OP-=(CO TTMA<Mod<MODULO> >& mat) NE{SIMD_Subtraction_32_128(m_M00,m_M01,m_M10,m_M11,mat.m_M00,mat.m_M01,mat.m_M10,mat.m_M11,m_M00,m_M01,m_M10,m_M11);RE *TH;}TE <> IN TTMA<MN<MODULO> >& TTMA<MN<MODULO> >::OP-=(CO TTMA<MN<MODULO> >& mat) NE{SIMD_Subtraction_32_128(m_M00,m_M01,m_M10,m_M11,mat.m_M00,mat.m_M01,mat.m_M10,mat.m_M11,m_M00,m_M01,m_M10,m_M11);RE *TH;}
TE <TY T>CL TTMA;TE <TY T>CL TOMA{PU:T m_M0;T m_M1;PU:CE TOMA(CO T& M0 = T(),CO T& M1 = T())NE;CE TOMA(T&& M0,T&& M1)NE;CE TOMA(CO TOMA<T>& mat)NE;CE TOMA(TOMA<T>&& mat)NE;CE TOMA<T>& OP=(CO TOMA<T>& mat)NE;CE TOMA<T>& OP=(TOMA<T>&& mat)NE;CE TOMA<T>& OP+=(CO TOMA<T>& mat)NE;CE TOMA<T>& OP-=(CO TOMA<T>& mat)NE;IN TOMA<T>& OP*=(CO TTMA<T>& mat)NE;CE TOMA<T>& OP*=(CO T& scalar)NE;TE <SFINAE_FOR_MA(= nullptr)> CE TOMA<T>& OP*=(CO Arg& scalar)NE;IN TOMA<T>& OP/=(CO T& scalar);TE <SFINAE_FOR_MA(= nullptr)> CE TOMA<T>& OP/=(CO Arg& scalar);IN TOMA<T>& OP%=(CO T& scalar);TE <SFINAE_FOR_MA(= nullptr)> CE TOMA<T>& OP%=(CO Arg& scalar);CE T& GetEntry(CRUI y) CO NE;CE T& RefEntry(CRUI y)NE;};
#define VECTRISATION_FOR_TTMA_FOR_MOD(TYPE,MODULO) TE <> IN TTMA<TYPE>& TTMA<TYPE>::OP+=(CO TTMA<TYPE>& mat)NE{uint TH_copy[4] ={m_M00.m_n,m_M01.m_n,m_M10.m_n,m_M11.m_n};uint mat_copy[4] ={mat.m_M00.m_n,mat.m_M01.m_n,mat.m_M10.m_n,mat.m_M11.m_n};__m128i v_sum = _mm_load_si128((__m128i*)this_copy) + _mm_load_si128((__m128i*)mat_copy );_mm_store_si128((__m128i*)this_copy,v_sum);uint dif[4];for(uint i = 0;i < 4;i++){dif[i] = this_copy[i] < MODULO?0:MODULO;}v_sum -= _mm_load_si128((__m128i*)dif);_mm_store_si128((__m128i*)this_copy,v_sum);m_M00.m_n = TH_copy[0];m_M01.m_n = TH_copy[1];m_M10.m_n = TH_copy[2];m_M11.m_n = TH_copy[3];RE *TH;}TE <> IN TTMA<TYPE>& TTMA<TYPE>::OP-=(CO TTMA<TYPE>& mat)NE{SET_CO_VE_32_128_FOR_SIMD(uint,M,MODULO);uint TH_copy[4] ={m_M00.m_n,m_M01.m_n,m_M10.m_n,m_M11.m_n};uint mat_copy[4] ={mat.m_M00.m_n,mat.m_M01.m_n,mat.m_M10.m_n,mat.m_M11.m_n};__m128i v_sub = _mm_load_si128((__m128i*)this_copy) + v_M - _mm_load_si128((__m128i*)mat_copy );_mm_store_si128((__m128i*)this_copy,v_sub);uint dif[4];for(uint i = 0;i < 4;i++){dif[i] = this_copy[i] < MODULO?0:MODULO;}v_sub -= _mm_load_si128((__m128i*)dif);_mm_store_si128((__m128i*)this_copy,v_sub);for(uint i = 0;i < 4;i++){Mod<MODULO>::Normalise(TH_copy[i]);}m_M00.m_n = TH_copy[0];m_M01.m_n = TH_copy[1];m_M10.m_n = TH_copy[2];m_M11.m_n = TH_copy[3];RE *TH;}
TE <TY T>CL TTMA{PU:T m_M00;T m_M01;T m_M10;T m_M11;PU:CE TTMA(CO T& M00,CO T& M01,CO T& M10,CO T& M11)NE;CE TTMA(T&& M00,T&& M01,T&& M10,T&& M11)NE;CE TTMA(CO T& n = T())NE;TE <SFINAE_FOR_MA(= nullptr)> CE TTMA(CO Arg& n)NE;CE TTMA(CO TTMA<T>& mat)NE;CE TTMA(TTMA<T>&& mat)NE;CE TTMA<T>& OP=(CO TTMA<T>& mat)NE;CE TTMA<T>& OP=(TTMA<T>&& mat)NE;IN TTMA<T>& OP+=(CO TTMA<T>& mat)NE;IN TTMA<T>& OP-=(CO TTMA<T>& mat)NE;IN TTMA<T>& OP*=(CO TTMA<T>& mat)NE;CE TTMA<T>& OP*=(CO T& scalar)NE;TE <SFINAE_FOR_MA(= nullptr)> CE TTMA<T>& OP*=(CO Arg& scalar)NE;IN TTMA<T>& OP/=(CO TTMA<T>& mat);IN TTMA<T>& OP/=(CO T& scalar);TE <SFINAE_FOR_MA(= nullptr)> CE TTMA<T>& OP/=(CO Arg& scalar);IN TTMA<T>& OP%=(CO T& scalar);TE <SFINAE_FOR_MA(= nullptr)> CE TTMA<T>& OP%=(CO Arg& scalar);IN TTMA<T>& Invert();IN TTMA<T> OP*(CO TTMA<T>& mat) CO NE;IN TOMA<T> OP*(CO TOMA<T>& mat) CO NE;IN TTMA<T> OP/(CO TTMA<T>& mat) CO;CE TTMA<T> Square() CO NE;CE T& GetEntry(CRUI y,CRUI x) CO NE;CE T& RefEntry(CRUI y,CRUI x)NE;};TE <TY T,SFINAE_FOR_MA(= nullptr)> CE TTMA<T> OP*(CO Arg& scalar,CO TTMA<T>& mat)NE;TE <TY T,SFINAE_FOR_MA(= nullptr)> CE TTMA<T> OP*(CO TTMA<T>& mat,CO T& scalar)NE;TE <TY T,SFINAE_FOR_MA(= nullptr)> IN TTMA<T> OP/(CO TTMA<T>& mat,CO Arg& scalar);TE <TY T,SFINAE_FOR_MA(= nullptr)> IN TTMA<T> OP%(CO TTMA<T>& mat,CO Arg& scalar);
TE <TY T> CE TOMA<T>::TOMA(CO T& M0,CO T& M1)NE:m_M0(M0),m_M1(M1){}TE <TY T> CE TOMA<T>::TOMA(T&& M0,T&& M1)NE:m_M0(MO(M0)),m_M1(MO(M1)){}TE <TY T> CE TOMA<T>::TOMA(CO TOMA<T>& mat)NE:m_M0(mat.m_M0),m_M1(mat.m_M1){}TE <TY T> CE TOMA<T>::TOMA(TOMA<T>&& mat)NE:m_M0(MO(mat.m_M0)),m_M1(MO(mat.m_M1)){}TE <TY T> CE TOMA<T>& TOMA<T>::OP=(CO TOMA<T>& mat)NE{if(&mat != TH){m_M0 = mat.m_M0;m_M1 = mat.m_M1;}RE *TH;}TE <TY T> CE TOMA<T>& TOMA<T>::OP=(TOMA<T>&& mat)NE{m_M0 = MO(mat.m_M0);m_M1 = MO(mat.m_M1);RE *TH;}TE <TY T> CE TOMA<T>& TOMA<T>::OP+=(CO TOMA<T>& mat)NE{m_M0 += mat.m_M0;m_M1 += mat.m_M1;RE *TH;}TE <TY T> CE TOMA<T>& TOMA<T>::OP-=(CO TOMA<T>& mat)NE{m_M0 -= mat.m_M0;m_M1 -= mat.m_M1;RE *TH;}TE <TY T> IN TOMA<T>& TOMA<T>::OP*=(CO TTMA<T>& mat)NE{RE OP=(mat * *TH);}TE <TY T> CE TOMA<T>& TOMA<T>::OP*=(CO T& scalar)NE{m_M0 *= scalar;m_M1 *= scalar;RE *TH;}TE <TY T> TE <SFINAE_FOR_MA()> CE TOMA<T>& TOMA<T>::OP*=(CO Arg& scalar)NE{RE OP*=(T(scalar));}TE <TY T> IN TOMA<T>& TOMA<T>::OP/=(CO T& scalar){m_M0 /= scalar;m_M1 /= scalar;RE *TH;}TE <TY T> TE <SFINAE_FOR_MA()> CE TOMA<T>& TOMA<T>::OP/=(CO Arg& scalar){RE OP/=(T(scalar));}TE <TY T> IN TOMA<T>& TOMA<T>::OP%=(CO T& scalar){m_M0 %= scalar;m_M1 %= scalar;RE *TH;}TE <TY T> TE <SFINAE_FOR_MA()> CE TOMA<T>& TOMA<T>::OP%=(CO Arg& scalar){RE OP%=(T(scalar));}TE <TY T> CE T& TOMA<T>::GetEntry(CRUI y) CO NE{RE y == 0?m_M0:m_M1;}TE <TY T> CE T& TOMA<T>::RefEntry(CRUI y)NE{RE y == 0?m_M0:m_M1;}
TE <TY T> CE 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> CE 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> CE TTMA<T>::TTMA(CO T& n) NE:m_M00(n),m_M01(),m_M10(),m_M11(n){}TE <TY T> TE <SFINAE_FOR_MA()> CE TTMA<T>::TTMA(CO Arg& n) NE:TTMA(T(n)){}
TE <TY T> CE 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> CE 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> CE 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> CE 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{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-=(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;RE *TH;}TE <TY T> IN TTMA<T>& TTMA<T>::OP*=(CO TTMA<T>& mat) NE{RE OP=(*TH * mat);}TE <TY T> CE TTMA<T>& TTMA<T>::OP*=(CO T& scalar) NE{m_M00 *= scalar;m_M01 *= scalar;m_M10 *= scalar;m_M11 *= scalar;RE *TH;}TE <TY T> TE <SFINAE_FOR_MA()> CE TTMA<T>& TTMA<T>::OP*=(CO Arg& scalar) NE{RE OP*=(T(scalar));}TE <TY T> IN TTMA<T>& TTMA<T>::OP/=(CO TTMA<T>& mat){RE OP=(*TH / mat);}TE <TY T> IN TTMA<T>& TTMA<T>::OP/=(CO T& scalar){RE OP*=(T(1) / scalar);}TE <TY T> TE <SFINAE_FOR_MA()> CE TTMA<T>& TTMA<T>::OP/=(CO Arg& scalar){RE OP/=(T(scalar));}TE <TY T> IN TTMA<T>& TTMA<T>::OP%=(CO T& scalar){m_M00 %= scalar;m_M01 %= scalar;m_M10 %= scalar;m_M11 %= scalar;RE *TH;}TE <TY T> TE <SFINAE_FOR_MA()> CE TTMA<T>& TTMA<T>::OP%=(CO Arg& scalar){RE OP%=(T(scalar));}TE <TY T> IN TTMA<T>& TTMA<T>::Invert(){CO T det_inv{T(1) / (m_M00 * m_M11 - m_M01 * m_M10)};swap(m_M00,m_M11);m_M01 = T() - m_M01;m_M11 = T() - m_M10;RE OP*=(det_inv);}
TE <TY T> IN TTMA<T> TTMA<T>::OP*(CO TTMA<T>& mat) CO NE{RE TTMA<T>(m_M00 * mat.m_M00 + m_M01 * mat.m_M10,m_M00 * mat.m_M01 + m_M01 * mat.m_M11,m_M10 * mat.m_M00 + m_M11 * mat.m_M10,m_M10 * mat.m_M01 + m_M11 * mat.m_M11);}TE <TY T> IN TOMA<T> TTMA<T>::OP*(CO TOMA<T>& mat) CO NE{RE TOMA<T>(m_M00 * mat.m_M0 + m_M01 * mat.m_M1,m_M10 * mat.m_M0 + m_M11 * mat.m_M1);}TE <TY T> IN TTMA<T> TTMA<T>::OP/(CO TTMA<T>& mat) CO{CO T det_inv{T(1) / (mat.m_M00 * mat.m_M11 - mat.m_M01 * mat.m_M10)};RE TTMA<T>((m_M00 * mat.m_M11 - m_M01 * mat.m_M10) * det_inv,(m_M01 * mat.m_M00 - m_M00 * mat.m_M01) * det_inv,(m_M10 * mat.m_M11 - m_M11 * mat.m_M10) * det_inv,(m_M11 * mat.m_M00 - m_M10 * mat.m_M01) * det_inv);}TE <TY T> CE TTMA<T> TTMA<T>::Square() CO NE{RE TTMA<T>(m_M00 * m_M00 + m_M01 * m_M10,(m_M00 + m_M11) * m_M01,m_M10 * (m_M00 + m_M11),m_M10 * m_M01 + m_M11 * m_M11);}TE <TY T> CE T& TTMA<T>::GetEntry(CRUI y,CRUI x) CO NE{RE y == 0?x == 0?m_M00:m_M01:x == 0?m_M10:m_M11;}TE <TY T> CE T& TTMA<T>::RefEntry(CRUI y,CRUI x) NE{RE y == 0?x == 0?m_M00:m_M01:x == 0?m_M10:m_M11;}
TE <TY T> IN TTMA<T> OP+(CO TTMA<T>& mat1,CO TTMA<T>& mat2) NE{RE MO(TTMA<T>(mat1) += mat2);}TE <TY T> IN TTMA<T> OP-(CO TTMA<T>& mat1,CO TTMA<T>& mat2) NE{RE MO(TTMA<T>(mat1) -= mat2);}TE <TY T> CE TTMA<T> OP*(CO T& scalar,CO TTMA<T>& mat) NE{RE MO(TTMA<T>(mat) *= scalar);}TE <TY T,SFINAE_FOR_MA()> CE TTMA<T> OP*(CO Arg& scalar,CO TTMA<T>& mat) NE{RE T(scalar) * mat;}TE <TY T> CE TTMA<T> OP*(CO TTMA<T>& mat,CO T& scalar) NE{RE MO(TTMA<T>(mat) *= scalar);}TE <TY T,SFINAE_FOR_MA()> CE TTMA<T> OP*(CO TTMA<T>& mat,CO Arg& scalar) NE{RE mat * T(scalar);}TE <TY T> IN TTMA<T> OP/(CO TTMA<T>& mat,CO T& scalar){RE MO(TTMA<T>(mat) /= scalar);}TE <TY T,SFINAE_FOR_MA()> IN TTMA<T> OP/(CO TTMA<T>& mat,CO Arg& scalar){RE mat / T(scalar);}TE <TY T> IN TTMA<T> OP%(CO TTMA<T>& mat,CO T& scalar){RE MO(TTMA<T>(mat) %= scalar);}TE <TY T,SFINAE_FOR_MA()> IN TTMA<T> OP%(CO TTMA<T>& mat,CO Arg& scalar){RE mat % T(scalar);}TE <TY T> CE TTMA<T> Square(CO TTMA<T>& mat) NE{RE mat.Square();}VEISATION_FOR_TTMA_FOR_MOD(P);

#define SFINAE_FOR_PO(DEFAULT) TY Arg,enable_if_t<is_constructible<T,decay_t<Arg> >::value>* DEFAULT

TE <TY T>CL PO{PU:VE<T> m_f;uint m_SZ;PU:IN PO();IN PO(CO T& t);IN PO(T&& t);TE <SFINAE_FOR_PO(= nullptr)> IN PO(CO Arg& n);IN PO(CO PO<T>& f);IN PO(PO<T>&& f);IN PO(CRUI i,CO T& t);IN PO(CRUI i,T&& t);TE <SFINAE_FOR_PO(= nullptr)> IN PO(CRUI i,CO Arg& n);IN PO(CO VE<T>& f);IN PO(VE<T>&& f);IN PO<T>& OP=(CO T& t);IN PO<T>& OP=(T&& t);TE <SFINAE_FOR_PO(= nullptr)> IN PO<T>& OP=(CO Arg& n);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;PO<T>& OP+=(CO PO<T>& f);PO<T>& OP-=(CO PO<T>& f);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> TPQuotient(CO PO<T>& f0,CRUI f0_TP_SZ,CO PO<T>& f1_TP_inverse,CRUI f1_SZ);ST PO<T> TP(CO PO<T>& f,CRUI f_TP_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();};

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(T&& t):PO(){if(t != CO_zero()){OP[](0) = MO(t);}}TE <TY T> TE <SFINAE_FOR_PO()> IN PO<T>::PO(CO Arg& n):PO(T(n)){}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(CRUI i,T&& t):PO(){if(t != CO_zero()){OP[](i) = MO(t);}}TE <TY T> TE <SFINAE_FOR_PO()> IN PO<T>::PO(CRUI i,CO Arg& n):PO(i,T(n)){}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=(T&& t){m_f.clear();m_SZ = 0;OP[](0) = MO(t);RE *TH;}TE <TY T> TE <SFINAE_FOR_PO()> IN PO<T>& PO<T>::OP=(CO Arg& n){RE OP=(T(n));}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>PO<T>& PO<T>::OP+=(CO PO<T>& f){if(m_SZ < f.m_SZ){m_f.reserve(f.m_SZ);for(uint i = 0;i < m_SZ;i++){m_f[i] += f.m_f[i];}for(uint i = m_SZ;i < f.m_SZ;i++){m_f.push_back(f.m_f[i]);}m_SZ = f.m_SZ;}else{for(uint i = 0;i < f.m_SZ;i++){m_f[i] += f.m_f[i];}}RE *TH;}TE <TY T>PO<T>& PO<T>::OP-=(CO PO<T>& f){if(m_SZ < f.m_SZ){m_f.reserve(f.m_SZ);for(uint i = 0;i < m_SZ;i++){m_f[i] -= f.m_f[i];}for(uint i = m_SZ;i < f.m_SZ;i++){m_f.push_back(- f.m_f[i]);}m_SZ = f.m_SZ;}else{for(uint i = 0;i < f.m_SZ;i++){m_f[i] -= f.m_f[i];}}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 uint SZ = m_SZ + f.m_SZ - 1;PO<T> product{};for(uint i = 0;i < SZ;i++){T& product_i = product[i];CO uint j_min = m_SZ > i?0:i - m_SZ + 1;CO uint j_lim = i < f.m_SZ?i + 1:f.m_SZ;for(uint j = j_min;j < j_lim;j++){product_i += m_f[i - j] * f.m_f[j];}}RE OP=(MO(product));}TE <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(uint i = 0;i < m_SZ;i++){OP[](i) *= t_inv;}RE *TH;}TE <TY T>PO<T> PO<T>::TP(CO PO<T>& f,CRUI f_TP_SZ){VE<T> f_TP(f_TP_SZ);for(uint d = 0;d < f_TP_SZ;d++){f_TP[d] = f.m_f[f.m_SZ - 1 - d];}RE PO<T>(MO(f_TP));}TE <TY T>PO<T>& PO<T>::OP%=(CO T& t){if(t == CO_one()){RE OP=(zero());}for(uint i = 0;i < m_SZ;i++){m_f[i] %= t;}RE *TH;}TE <TY T> IN PO<T> PO<T>::OP-() CO{RE MO(PO<T>() -= *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(uint i = 1;i < m_SZ;i++){s += "," + to_string(m_f[i]);}}s += ")";RE s;}TE <TY T> IN CO PO<T>& PO<T>::zero(){ST CO PO<T> z{};RE z;}TE <TY T> IN CO T& PO<T>::CO_zero(){ST CO T z{0};RE z;}TE <TY T> IN CO T& PO<T>::CO_one(){ST CO T o{1};RE o;}TE <TY T> IN CO T& PO<T>::CO_minus_one(){ST CO T m{-1};RE m;}TE <TY T>bool OP==(CO PO<T>& f0,CO T& t1){CRUI SZ = f0.SZ();CO T& zero = PO<T>::CO_zero();for(uint i = 1;i < SZ;i++){if(f0[i] != zero){RE false;}}RE f0[0] == t1;}TE <TY T>bool OP==(CO PO<T>& f0,CO PO<T>& f1){CRUI SZ0 = f0.SZ();CRUI SZ1 = f1.SZ();CRUI SZ = SZ0 < SZ1?SZ1:SZ0;for(uint i = 0;i < SZ;i++){if(f0[i] != f1[i]){RE false;}}RE true;}TE <TY T,TY P> IN bool 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,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 IT = f.BE(),EN = f.EN();WH(IT != EN){T& t = *IT;IT++;if(IT != EN){t *= *IT;IT = f.erase(IT);}}RE Prod(f);}
TE <TY T,uint EX_lim>CL PW_CE{PU:T m_val[EX_lim];IN CE PW_CE(CO T& t,CO T& init = T(1));};TE <TY T,uint EX_lim> IN CE PW_CE<T,EX_lim>::PW_CE(CO T& t,CO T& init):m_val() {T PW{init};for( uint EX = 0;EX < EX_lim;EX++){m_val[EX] = PW;PW *= t;}}

US MNPN = PO<MNP>;US MNPNK = PO<MNPN>;IN CEXPR(int,fold_digit,5);IN CEXPR(int,fold,1 << fold_digit);IN CEXPR(int,deg_max,fold + 1);IN CEXPR(int,deg_lim,deg_max + 1);
#define SET_CEXPR(NUM) CE MNP c ## NUM{MNP::DeRP(NUM)};
#define HONTAI MNP Ntd[fold + 1] ={c1};MNP Nt1{Nt};MNP Nt_power{c1};FOREQ(d,1,fold){Ntd[d] =(Nt_power *= Nt1);}TTMA<MNP> diff[deg_lim] ={};TTMA<MNP>& MNk = diff[0];FOREQ(deg,0,deg_max){TTMA<MNP> &diff_deg = diff[deg];MNP* p_diff_deg[4] ={&(diff_deg.m_M00),&(diff_deg.m_M01),&(diff_deg.m_M10),&(diff_deg.m_M11)};vector<uint>(&TheAtsu_coef_deg)[4] = TheAtsu_coef[deg];vector<uint>(&TheAtsu_degree_deg)[4] = TheAtsu_degree[deg];FOR(i,0,4){MNP& diff_deg_i = *p_diff_deg[i];vector<uint>& TheAtsu_coef_deg_i = TheAtsu_coef_deg[i];vector<uint>& TheAtsu_degree_deg_i = TheAtsu_degree_deg[i];uint TheAtsu_coef_deg_i_SZ = TheAtsu_coef_deg_i.SZ();FOR(d,0,TheAtsu_coef_deg_i_SZ){diff_deg_i += Ntd[TheAtsu_degree_deg_i[d]] * coef_array[TheAtsu_coef_deg_i[d]];}}}TOMA<MNP> vt{v};uint Kt_div = Kt >> fold_digit;REPEAT(Kt_div){TTMA<MNP>* p_M_diff = &MNk;TTMA<MNP>* p_M = p_M_diff++;vt *= MNk;FOR(deg,0,deg_max){*(p_M++) += *(p_M_diff++);}}uint k_start = Kt_div << fold_digit;MNP k_start_1{MNP::DeRP(k_start)};MNP Nt1_minus_k_start_1{Nt1 - k_start_1};MNk.m_M00 = Twice(Nt1_minus_k_start_1);MNk.m_M01 =((k_start & 1) == 0?k_start == 0?MNP(c0):move(((Twice(Nt1) -= k_start_1) += c1) *= MNP::DeRP(k_start >> 1)):move(((c1 - k_start_1).Halve() += Nt1) *= k_start_1));MNk.m_M10 = c1;MNk.m_M11 = c0;MNP diff01{Nt1_minus_k_start_1};FOR(k,k_start,Kt){vt *= MNk;MNk.m_M00 -= c2;MNk.m_M01 += diff01--;}COUT(vt.m_M0);
MAIN()
{
  UNTIE;
  CEXPR( uint , bound_T , 100000 );
  CIN_ASSERT( T , 1 , bound_T );
  // 本体を定数倍改善するための前計算
  SET_CEXPR( 0 );
  SET_CEXPR( 1 );
  SET_CEXPR( 2 );
  constexpr MNP c2_neg{ MNP::DeRP( P - 2 ) };
  constexpr MNP c2_inv{ MNP::DeRP( ( P + 1 ) / 2 ) };
  constexpr MNP c2_inv_neg{ MNP::DeRP( ( P - 1 ) / 2 ) };
  const MNPN& zero = MNPN::zero();
  const MNPN one{ 0 , c1 };
  const MNPN two{ 0 , c2 };
  const MNPN two_inv{ 0 , c2_inv };
  constexpr TOMA<MNP> v{ MNP::DeRP( 1 ) , MNP::DeRP( 0 ) };
  TTMA<MNPNK> MNk_shift
  { move( MNPNK( 1 , MNPN( 0 , c2_neg ) ) += MNPNK( 0 , MNPN( 1 , c2 ) ) ) , move( MNPNK( 2 , MNPN( 0 , c2_inv_neg ) ) += MNPNK( 1 , move( MNPN( 1 , c1 ) += c2_inv ) ) ) ,
      MNPNK( 0 , one ) , MNPNK( 0 , zero ) };
  list<TTMA<MNPNK> > M = {};
  CEXPR( int , fold_minus , fold - 1 );
  REPEAT( fold_minus ){
    M.push_front( MNk_shift );
    MNk_shift.m_M00.m_f[0] -= two;
    MNk_shift.m_M01.m_f[0] += ( MNk_shift.m_M01.m_f[1] -= one ) + two_inv;
  }
  M.push_front( move( MNk_shift ) );
  vector<MNPN> comb[deg_lim] = {};
  comb[0].push_back( one );
  FOREQ( deg , 1 , deg_max ){
    MNPN* p_comb_deg_minus_right = &( comb[deg - 1][0] );
    MNPN* p_comb_deg_minus_left = p_comb_deg_minus_right++;
    vector<MNPN>& comb_deg = comb[deg];
    comb_deg = vector<MNPN>( deg + 1 ,  zero );
    comb_deg[0] = comb_deg[deg] = one;
    uint deg_half = ( deg + 1 ) / 2;
    FOR( ddeg , 1 , deg_half ){
      comb_deg[ddeg] = comb_deg[deg - ddeg] = *p_comb_deg_minus_left + *p_comb_deg_minus_right;
      p_comb_deg_minus_left++;
      p_comb_deg_minus_right++;
    }
    if( deg % 2 == 0 ){
      comb_deg[deg_half] = *p_comb_deg_minus_left + *p_comb_deg_minus_left;
    }
  }
  constexpr PW_CE<MNP,deg_lim> fp{ fold };
  MNPN fp1[deg_lim];
  FOREQ( deg , 0 , deg_max ){
    fp1[deg] = MNPN( 0 , fp.m_val[deg] );
  }
  vector<vector<MNPN> > comb_fp{};
  comb_fp.reserve( deg_lim );
  comb_fp.push_back( vector<MNPN>() );
  FOR( ddeg , 1 , deg_lim ){
    vector<MNPN>& comb_ddeg = comb[ddeg];
    comb_fp.push_back( vector<MNPN>() );
    vector<MNPN>& comb_fp_ddeg = comb_fp[ddeg];
    comb_fp_ddeg.reserve( ddeg );
    comb_fp_ddeg.push_back( fp1[ddeg] );
    FOR( dddeg , 1 , ddeg ){
      comb_fp_ddeg.push_back( comb_ddeg[dddeg] * fp1[ddeg - dddeg] );
    }
  }
  TTMA<MNPNK> prod[deg_lim];
  TTMA<MNPNK>& prod_curr = prod[deg_max];
  prod_curr = Prod( M );
  MNPNK* p_prod_curr[4] = { &( prod_curr.m_M00 ) , &( prod_curr.m_M01 ) , &( prod_curr.m_M10 ) , &( prod_curr.m_M11 ) };
  FOR( deg , 0 , deg_max ){
    prod[deg] = prod_curr;
    FOR( i , 0 , 4 ){
      MNPNK& prod_curr_i = *( p_prod_curr[i] );
      const uint& size = prod_curr_i.size();
      FOR( ddeg , 1 , size ){
	vector<MNPN>& comb_fp_ddeg = comb_fp[ddeg];
	MNPN& prod_curr_i_ddeg = prod_curr_i.m_f[ddeg];
	FOR( dddeg , 0 , ddeg ){
	  prod_curr_i.m_f[dddeg] += prod_curr_i_ddeg * comb_fp_ddeg[dddeg];
	}
      }
    }
  }
  // 愚直代入版（fold=32固定なのでO(max(K)T)）
  // fold = 32の場合のcoefに必要のサイズの前計算値
  CEXPR( uint , coef_size_max , 33 );
  // ここはvector<uint>よりuint[coef_size_max]の方が僅かに速い
  uint coef[deg_lim][4][coef_size_max];
  uint coef_size[deg_lim][4] = {};
  map<uint,uint> coef_list{};
  FOREQ( deg , 0 , deg_max ){
    TTMA<MNPNK>& diff_deg = prod[deg];
    MNPN* p_diff_deg[4] = { &( diff_deg.m_M00[0] ) , &( diff_deg.m_M01[0] ) , &( diff_deg.m_M10[0] ) , &( diff_deg.m_M11[0] ) };
    uint ( &coef_deg )[4][coef_size_max] = coef[deg];
    uint ( &coef_size_deg )[4] = coef_size[deg];
    FOR( i , 0 , 4 ){
      MNPN& diff_deg_i = *( p_diff_deg[i] );
      const uint& size = diff_deg_i.size();
      uint ( &coef_deg_i )[coef_size_max] = coef_deg[i];
      uint& coef_size_deg_i = coef_size_deg[i];
      FOR( d , 0 , size ){
	const uint& diff_deg_i_d = diff_deg_i[d].RP(); 
	coef_deg_i[coef_size_deg_i++] = diff_deg_i_d;
	if( diff_deg_i_d > 0 ){
	  coef_list[diff_deg_i_d];
	}
      }
    }
    TTMA<MNPNK>* p_prod_curr = &( prod[deg_max] );
    TTMA<MNPNK>* p_prod_prev = p_prod_curr--;
    FOREQ( ddeg_trans , deg + 1 , deg_max ){
      *p_prod_prev -= *p_prod_curr;
      p_prod_prev->m_M00.ReMORedundantZero();
      p_prod_prev->m_M01.ReMORedundantZero();
      p_prod_prev->m_M10.ReMORedundantZero();
      p_prod_prev->m_M11.ReMORedundantZero();
      p_prod_curr--;
      p_prod_prev--;
    }
  }
  // fold = 32の時のcoef_list.size()の前計算値
  CEXPR( uint , coef_list_size , 2176 );
  // ここはvector<uint>よりuint[coef_list_size]の方が僅かに速い
  MNP coef_array[coef_list_size];
  uint coef_array_size = 0;
  FOR_ITR( coef_list , itr , end ){
    coef_array[itr->second = coef_array_size++] = MNP::DeRP( itr->first );
  }
  // 係数0をスキップで1.1倍、座標圧縮で1.05倍くらい早くなる。
  // ここをvector<uint>でなくuint[coef_size_max]にすると逆に遅くなる。
  vector<uint> TheAtsu_coef[deg_lim][4] = {};
  vector<uint> TheAtsu_degree[deg_lim][4] = {};
  FOREQ( deg , 0 , deg_max ){
    uint ( &coef_deg )[4][coef_size_max] = coef[deg];
    uint ( &coef_size_deg )[4] = coef_size[deg];
    vector<uint> ( &TheAtsu_coef_deg )[4] = TheAtsu_coef[deg];
    vector<uint> ( &TheAtsu_degree_deg )[4] = TheAtsu_degree[deg];
    FOR( i , 0 , 4 ){
      uint ( &coef_deg_i )[coef_size_max] = coef_deg[i];
      uint& coef_size_deg_i = coef_size_deg[i];
      vector<uint>& TheAtsu_coef_deg_i = TheAtsu_coef_deg[i];
      vector<uint>& TheAtsu_degree_deg_i = TheAtsu_degree_deg[i];
      TheAtsu_coef_deg_i.reserve( coef_size_deg_i );
      TheAtsu_degree_deg_i.reserve( coef_size_deg_i );
      FOR( d , 0 , coef_size_deg_i ){
	uint& coef_deg_i_d = coef_deg_i[d];
	if( coef_deg_i_d != 0 ){
	  TheAtsu_coef_deg_i.push_back( coef_list[coef_deg_i_d] );
	  TheAtsu_degree_deg_i.push_back( d );
	}
      }
    }
  }
  // ここから本体
  CEXPR( ull , bound_N , 1000000000000000000 );
  if( T > 5 ){
    CEXPR( uint , bound_K1 , bound_T );
    REPEAT( T ){
      CIN_ASSERT( Nt , 1 , bound_N );
      CIN_ASSERT( Kt , 0 , bound_K1 );
      HONTAI;
    }
  } else {
    CEXPR( ull , bound_K2 , bound_N );
    REPEAT( T ){
      CIN_ASSERT( Nt , 1 , bound_N );
      CIN_ASSERT( Ktull , 0 , bound_K2 );
      if( Ktull >= P ){
	COUT( 0 );
      } else {
	uint Kt = uint( Ktull );
	HONTAI;
      }
    }
  }
  return 0;
}