#include <bits/stdc++.h>
#include <immintrin.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;

#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#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 CO LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; ++ VAR )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; ++ VAR )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; -- VAR )
#define FOR_IT( ARRAY , IT , EN ) for( auto IT = ARRAY .BE() , EN = ARRAY .EN() ; IT != EN ; ++ IT )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define COUT( AN ) cout << ( AN ) << "\n"


US ull = unsigned long long;

IN CEXPR( uint , P , 998244353 );

TE <uint M , TY INT> IN CE INT& RS( INT& n ) NE { RE n < 0 ? ( ( ( ( ++n ) *= -1 ) %= M ) *= -1 ) += M - 1 : n %= M; }
TE <uint M> IN CE uint& RS( uint& n ) NE { RE n %= M; }
TE <uint M> IN CE ull& RS( ull& n ) NE { RE n %= M; }
TE <TY INT> IN CE INT& RSP( INT& n ) NE { CE CO 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 <> IN CE ull& RS<P,ull>( ull& n ) NE { CE CO ull Pull = P; CE CO ull Pull2 = ( Pull - 1 ) * ( Pull - 1 ); RE RSP( n > Pull2 ? n -= Pull2 : n ); }

TE <uint M , TY INT> IN CE INT RS( INT&& n ) NE { RE MO( RS<M>( n ) ); }
TE <uint M , TY INT> IN 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:
IN CE Mod() NE;
IN CE Mod( CO Mod<M>& n ) NE;
IN CE Mod( Mod<M>& n ) NE;
IN CE Mod( Mod<M>&& n ) NE;
TE <SFINAE_FOR_MOD( = nullptr )> IN CE Mod( CO T& n ) NE;
TE <SFINAE_FOR_MOD( = nullptr )> IN CE Mod( T& n ) NE;
TE <SFINAE_FOR_MOD( = nullptr )> IN CE Mod( T&& n ) NE;

IN CE Mod<M>& OP=( CO Mod<M>& n ) NE;
IN CE Mod<M>& OP=( Mod<M>&& n ) NE;
IN CE Mod<M>& OP+=( CO Mod<M>& n ) NE;
IN CE Mod<M>& OP-=( CO Mod<M>& n ) NE;
IN CE Mod<M>& OP*=( CO Mod<M>& n ) NE;
IN Mod<M>& OP/=( CO Mod<M>& n );
IN CE Mod<M>& OP<<=( int n ) NE;

IN CE Mod<M>& OP>>=( int n ) NE;

IN CE Mod<M>& OP++() NE;
IN CE Mod<M> OP++( int ) NE;
IN CE Mod<M>& OP--() NE;
IN 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( / );
IN CE Mod<M> OP<<( int n ) CO NE;
IN CE Mod<M> OP>>( int n ) CO NE;

IN CE Mod<M> OP-() CO NE;
IN CE Mod<M>& SignInvert() NE;
IN CE Mod<M>& Double() NE;

IN CE Mod<M>& Halve() NE;

IN Mod<M>& Invert();
TE <TY T> IN CE Mod<M>& PositivePW( T&& EX ) NE;
TE <TY T> IN CE Mod<M>& NonNegativePW( T&& EX ) NE;

TE <TY T> IN CE Mod<M>& PW( T&& EX );

IN CE VO swap( Mod<M>& n ) NE;

IN CE CO uint& RP() CO NE;


ST IN CE Mod<M> DeRP( CO uint& n ) NE;
ST IN 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> IN 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:
IN CE MN() NE;
IN CE MN( CO MN<M>& n ) NE;
IN CE MN( MN<M>& n ) NE;
IN CE MN( MN<M>&& n ) NE;
TE <SFINAE_FOR_MN( = nullptr )> IN CE MN( CO T& n ) NE;
TE <SFINAE_FOR_MN( = nullptr )> IN CE MN( T&& n ) NE;

IN CE MN<M>& OP=( CO MN<M>& n ) NE;
IN CE MN<M>& OP=( MN<M>&& n ) NE;
IN CE MN<M>& OP+=( CO MN<M>& n ) NE;
IN CE MN<M>& OP-=( CO MN<M>& n ) NE;
IN CE MN<M>& OP*=( CO MN<M>& n ) NE;
IN MN<M>& OP/=( CO MN<M>& n );
IN CE MN<M>& OP<<=( int n ) NE;

IN CE MN<M>& OP>>=( int n ) NE;

IN CE MN<M>& OP++() NE;
IN CE MN<M> OP++( int ) NE;
IN CE MN<M>& OP--() NE;
IN 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( / );
IN CE MN<M> OP<<( int n ) CO NE;
IN CE MN<M> OP>>( int n ) CO NE;

IN CE MN<M> OP-() CO NE;
IN CE MN<M>& SignInvert() NE;
IN CE MN<M>& Double() NE;

IN CE MN<M>& Halve() NE;

IN CE MN<M>& Invert();
TE <TY T> IN CE MN<M>& PositivePW( T&& EX ) NE;
TE <TY T> IN CE MN<M>& NonNegativePW( T&& EX ) NE;

TE <TY T> IN CE MN<M>& PW( T&& EX );

IN CE uint RP() CO NE;
IN CE Mod<M> Reduce() CO NE;


ST IN 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 IN CE uint Form( CO uint& n ) NE;
ST IN CE ull& Reduction( ull& n ) NE;
ST IN CE ull& ReducedMU( ull& n , CO uint& m ) NE;
ST IN CE uint MU( CO uint& n0 , CO uint& n1 ) NE;
ST IN CE uint BaseSquareTruncation( uint& n ) NE;

TE <TY T> IN CE MN<M>& Ref( T&& n ) NE;

};

TE <uint M>
CL COantsForMod
{

PU:
COantsForMod() = delete;
ST CE CO bool g_even = ( ( M & 1 ) == 0 );
ST CE CO uint g_memory_bound = 1000000;
ST CE CO uint g_memory_LE = M < g_memory_bound ? M : g_memory_bound;

ST IN 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 CO int g_MN_digit = 32;
ST CE CO ull g_MN_base = ull( 1 ) << g_MN_digit;
ST CE CO uint g_MN_base_minus = uint( g_MN_base - 1 );
ST CE CO uint g_MN_digit_half = ( g_MN_digit + 1 ) >> 1;
ST CE CO uint g_MN_base_sqrt_minus = ( 1 << g_MN_digit_half ) - 1;
ST CE CO uint g_MN_M_neg_inverse = uint( ( g_MN_base - MNBasePW( ( ull( 1 ) << ( g_MN_digit - 1 ) ) - 1 ) ) & g_MN_base_minus );
ST CE CO uint g_MN_base_mod = uint( g_MN_base % M );
ST CE CO uint g_MN_base_square_mod = uint( ( ( g_MN_base % M ) * ( g_MN_base % M ) ) % M );

};

TE <uint M> IN 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; }


TE <uint M> IN 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> IN CE ull& MN<M>::Reduction( ull& n ) NE { RE ( ( n += ull( uint( n ) * COantsForMod<M>::g_MN_M_neg_inverse ) * M ) >>= COantsForMod<M>::g_MN_digit ) < M ? n : n -= M; }
TE <uint M> IN CE ull& MN<M>::ReducedMU( ull& n , CO uint& m ) NE { RE Reduction( n *= m ); }
TE <uint M> IN 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> IN 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> IN CE MN<M>::MN() NE : Mod<M>() { static_assert( ! COantsForMod<M>::g_even ); }
TE <uint M> IN CE MN<M>::MN( CO MN<M>& n ) NE : Mod<M>( n ) {}
TE <uint M> IN CE MN<M>::MN( MN<M>& n ) NE : Mod<M>( n ) {}
TE <uint M> IN CE MN<M>::MN( MN<M>&& n ) NE : Mod<M>( MO( n ) ) {}
TE <uint M> TE <SFINAE_FOR_MN()> IN 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()> IN 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> IN CE MN<M>& MN<M>::OP=( CO MN<M>& n ) NE { RE Ref( Mod<M>::OP=( n ) ); }
TE <uint M> IN CE MN<M>& MN<M>::OP=( MN<M>&& n ) NE { RE Ref( Mod<M>::OP=( MO( n ) ) ); }

TE <uint M> IN CE MN<M>& MN<M>::OP+=( CO MN<M>& n ) NE { RE Ref( Mod<M>::OP+=( n ) ); }
TE <uint M> IN CE MN<M>& MN<M>::OP-=( CO MN<M>& n ) NE { RE Ref( Mod<M>::OP-=( n ) ); }
TE <uint M> IN 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> IN CE MN<M>& MN<M>::OP<<=( int n ) NE { RE Ref( Mod<M>::OP<<=( n ) ); }
TE <uint M> IN CE MN<M>& MN<M>::OP>>=( int n ) NE { RE Ref( Mod<M>::OP>>=( n ) ); }

TE <uint M> IN 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> IN CE MN<M> MN<M>::OP++( int ) NE { MN<M> n{ *TH }; OP++(); RE n; }
TE <uint M> IN 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> IN 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> IN CE MN<M> MN<M>::OP<<( int n ) CO NE { RE MO( MN<M>( *TH ) <<= n ); }
TE <uint M> IN CE MN<M> MN<M>::OP>>( int n ) CO NE { RE MO( MN<M>( *TH ) >>= n ); }

TE <uint M> IN CE MN<M> MN<M>::OP-() CO NE { RE MO( MN<M>( *TH ).SignInvert() ); }
TE <uint M> IN 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> IN CE MN<M>& MN<M>::Double() NE { RE Ref( Mod<M>::Double() ); }
TE <uint M> IN CE MN<M>& MN<M>::Halve() NE { RE Ref( Mod<M>::Halve() ); }

TE <uint M> IN 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> IN 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> IN 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> IN 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> IN CE uint MN<M>::RP() CO NE { ull m_n_copy = Mod<M>::m_n; RE MO( Reduction( m_n_copy ) ); }
TE <uint M> IN 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> IN 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 CO MN<M> z{}; RE z; }
TE <uint M> IN CO MN<M>& MN<M>::one() NE { ST CE CO MN<M> o{ DeRP( 1 ) }; RE o; }

TE <uint M> TE <TY T> IN CE MN<M>& MN<M>::Ref( T&& n ) NE { RE *TH; }

TE <uint M> IN CE MN<M> Twice( CO MN<M>& n ) NE { RE MO( MN<M>( n ).Double() ); }
TE <uint M> IN CE MN<M> Half( CO MN<M>& n ) NE { RE MO( MN<M>( n ).Halve() ); }

TE <uint M> IN CE MN<M> Inverse( CO MN<M>& n ) { RE MO( MN<M>( n ).Invert() ); }

TE <uint M , TY T> IN CE MN<M> PW( CO MN<M>& n , CO T& EX ) { RE MO( MN<M>( n ).PW( T( EX ) ) ); }

TE <uint M> IN 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(); }

US MP = Mod<P>;
US MNP = MN<P>;

TE <uint M> IN CE Mod<M>::Mod() NE : m_n() {}
TE <uint M> IN CE Mod<M>::Mod( CO Mod<M>& n ) NE : m_n( n.m_n ) {}
TE <uint M> IN CE Mod<M>::Mod( Mod<M>& n ) NE : m_n( n.m_n ) {}
TE <uint M> IN CE Mod<M>::Mod( Mod<M>&& n ) NE : m_n( MO( n.m_n ) ) {}
TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod( CO T& n ) NE : m_n( RS<M>( n ) ) {}

TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod( T& n ) NE : m_n( RS<M>( decay_t<T>( n ) ) ) {}
TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod( T&& n ) NE : m_n( RS<M>( forward<T>( n ) ) ) {}


TE <uint M> IN CE Mod<M>& Mod<M>::OP=( CO Mod<M>& n ) NE { RE Ref( m_n = n.m_n ); }
TE <uint M> IN CE Mod<M>& Mod<M>::OP=( Mod<M>&& n ) NE { RE Ref( m_n = MO( n.m_n ) ); }

TE <uint M> IN CE Mod<M>& Mod<M>::OP+=( CO Mod<M>& n ) NE { RE Ref( Normalise( m_n += n.m_n ) ); }
TE <uint M> IN 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> IN 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 <> IN CE Mod<P>& Mod<P>::OP*=( CO Mod<P>& 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> IN CE Mod<M>& Mod<M>::OP<<=( int n ) NE { WH( n-- > 0 ){ Normalise( m_n <<= 1 ); } RE *TH; }
TE <uint M> IN 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> IN CE Mod<M>& Mod<M>::OP++() NE { RE Ref( m_n < COantsForMod<M>::g_M_minus ? ++m_n : m_n = 0 ); }
TE <uint M> IN CE Mod<M> Mod<M>::OP++( int ) NE { Mod<M> n{ *TH }; OP++(); RE n; }
TE <uint M> IN CE Mod<M>& Mod<M>::OP--() NE { RE Ref( m_n == 0 ? m_n = COantsForMod<M>::g_M_minus : --m_n ); }
TE <uint M> IN 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> IN CE Mod<M> Mod<M>::OP<<( int n ) CO NE { RE MO( Mod<M>( *TH ) <<= n ); }
TE <uint M> IN CE Mod<M> Mod<M>::OP>>( int n ) CO NE { RE MO( Mod<M>( *TH ) >>= n ); }

TE <uint M> IN CE Mod<M> Mod<M>::OP-() CO NE { RE MO( Mod<M>( *TH ).SignInvert() ); }
TE <uint M> IN CE Mod<M>& Mod<M>::SignInvert() NE { RE Ref( m_n > 0 ? m_n = M - m_n : m_n ); }


TE <uint M> IN CE Mod<M>& Mod<M>::Double() NE { RE Ref( Normalise( m_n <<= 1 ) ); }
TE <uint M> IN 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> IN 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> IN CE Mod<2>& Mod<2>::PositivePW( T&& EX ) NE { RE *TH; }
TE <uint M> TE <TY T> IN 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> IN 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> IN CE VO Mod<M>::swap( Mod<M>& n ) NE { std::swap( m_n , n.m_n ); }

TE <uint M> IN CE CO uint& Mod<M>::RP() CO NE { RE m_n; }

TE <uint M> IN 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> IN 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 CO Mod<M> z{}; RE z; }
TE <uint M> IN CO Mod<M>& Mod<M>::one() NE { ST CE CO Mod<M> o{ DeRP( 1 ) }; RE o; }

TE <uint M> TE <TY T> IN CE Mod<M>& Mod<M>::Ref( T&& n ) NE { RE *TH; }

TE <uint M> IN CE Mod<M> Twice( CO Mod<M>& n ) NE { RE MO( Mod<M>( n ).Double() ); }
TE <uint M> IN 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> IN 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> IN CE Mod<M> PW( CO Mod<M>& n , CO T& EX ) { RE MO( Mod<M>( n ).PW( T( EX ) ) ); }

TE <uint M> IN 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(); }


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; } }


#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>
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 );


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>
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> 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> 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 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 );

}

#define SET_VE_32_128_FOR_SIMD( UINT , VE_NAME , SCALAR0 , SCALAR1 , SCALAR2 , SCALAR3 ) CE CO 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 CO 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 CO 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 );

}

IN 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;

}


TE <uint M> __attribute__( ( target( "avx" ) ) ) IN VO SIMD_MU_32_128( CO MN<M>& a0 , CO MN<M>& a1 , CO MN<M>& a2 , CO MN<M>& a3 , CO MN<M>& b0 , CO MN<M>& b1 , CO MN<M>& b2 , CO MN<M>& b3 , MN<M>& c0 , MN<M>& c1 , MN<M>& c2 , MN<M>& c3 ) NE
{

ull aull_copy[4] = { a0.Mod<M>::m_n , a1.Mod<M>::m_n , a2.Mod<M>::m_n , a3.Mod<M>::m_n };
ull bull_copy[4] = { b0.Mod<M>::m_n , b1.Mod<M>::m_n , b2.Mod<M>::m_n , b3.Mod<M>::m_n };
__m256i v_aull = _mm256_load_si256( (__m256i*)aull_copy );
_mm256_store_si256( (__m256i*)aull_copy , v_aull *= _mm256_load_si256( (__m256i*)bull_copy ) );

ST CO __m128i& v_M_neg_inverse = COantsForSIMDForMod<M>::v_M_neg_inverse();
uint a_copy[4] = { uint( aull_copy[0] ) , uint( aull_copy[1] ) , uint( aull_copy[2] ) , uint( aull_copy[3] ) };
_mm_store_si128( (__m128i*)a_copy , _mm_mullo_epi32( _mm_load_si128( (__m128i*)a_copy ) , v_M_neg_inverse ) );

SET_CO_VE_64_256_FOR_SIMD( ull , Mull , M );
SET_CO_VE_64_256_FOR_SIMD( ull , digitull , COantsForMod<M>::g_MN_digit );
bull_copy[0] = a_copy[0];
bull_copy[1] = a_copy[1];
bull_copy[2] = a_copy[2];
bull_copy[3] = a_copy[3];
( v_aull += _mm256_load_si256( (__m256i*)bull_copy ) * v_Mull ) >>= v_digitull;
_mm256_store_si256( (__m256i*)aull_copy , v_aull );

a_copy[0] = MO( aull_copy[0] );
a_copy[1] = MO( aull_copy[1] );
a_copy[2] = MO( aull_copy[2] );
a_copy[3] = MO( aull_copy[3] );
uint diff[4];


for( uint i = 0 ; i < 4 ; i++ ){

diff[i] = a_copy[i] < M ? 0 : M;

}

__m128i v_a = _mm_load_si128( (__m128i*)a_copy );
_mm_store_si128( (__m128i*)a_copy , v_a -= _mm_load_si128( (__m128i*)diff ) );
c0.Mod<M>::m_n = MO( a_copy[0] );
c1.Mod<M>::m_n = MO( a_copy[1] );
c2.Mod<M>::m_n = MO( a_copy[2] );
c3.Mod<M>::m_n = MO( a_copy[3] );
RE;

}

#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:
IN CE TOMA( CO T& M0 = T() , CO T& M1 = T() ) NE;
IN CE TOMA( T&& M0 , T&& M1 ) NE;
ATT IN CE TOMA( CO TOMA<T>& mat ) NE;
ATT IN CE TOMA( TOMA<T>&& mat ) NE;

ATT IN CE TOMA<T>& OP=( CO TOMA<T>& mat ) NE;
ATT IN CE TOMA<T>& OP=( TOMA<T>&& mat ) NE;
ATT IN CE TOMA<T>& OP+=( CO TOMA<T>& mat ) NE;
ATT IN CE TOMA<T>& OP-=( CO TOMA<T>& mat ) NE;

ATT IN TOMA<T>& OP*=( CO TTMA<T>& mat ) NE;
ATT IN CE TOMA<T>& OP*=( CO T& scalar ) NE;
TE <SFINAE_FOR_MA( = nullptr )> IN CE TOMA<T>& OP*=( CO Arg& scalar ) NE;
IN TOMA<T>& OP/=( CO T& scalar );
TE <SFINAE_FOR_MA( = nullptr )> IN CE TOMA<T>& OP/=( CO Arg& scalar );
IN TOMA<T>& OP%=( CO T& scalar );
TE <SFINAE_FOR_MA( = nullptr )> IN CE TOMA<T>& OP%=( CO Arg& scalar );


IN CE CO T& GetEntry( CRUI y ) CO NE;
IN CE T& RefEntry( CRUI y ) NE;

};

TE <TY T>
CL TTMA
{

PU:
T m_M00;
T m_M01;
T m_M10;
T m_M11;

PU:
IN CE TTMA( CO T& M00 , CO T& M01 , CO T& M10 , CO T& M11 ) NE;
IN CE TTMA( T&& M00 , T&& M01 , T&& M10 , T&& M11 ) NE;
IN CE TTMA( CO T& n = T() ) NE;
TE <SFINAE_FOR_MA( = nullptr )> IN CE TTMA( CO Arg& n ) NE;
ATT IN CE TTMA( CO TTMA<T>& mat ) NE;
ATT IN CE TTMA( TTMA<T>&& mat ) NE;

ATT IN CE TTMA<T>& OP=( CO TTMA<T>& mat ) NE;
ATT IN CE TTMA<T>& OP=( TTMA<T>&& mat ) NE;
ATT IN TTMA<T>& OP+=( CO TTMA<T>& mat ) NE;
ATT IN TTMA<T>& OP-=( CO TTMA<T>& mat ) NE;
ATT IN TTMA<T>& OP*=( CO TTMA<T>& mat ) NE;
ATT IN CE TTMA<T>& OP*=( CO T& scalar ) NE;
TE <SFINAE_FOR_MA( = nullptr )> ATT IN 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 )> IN CE TTMA<T>& OP/=( CO Arg& scalar );
IN TTMA<T>& OP%=( CO T& scalar );
TE <SFINAE_FOR_MA( = nullptr )> IN CE TTMA<T>& OP%=( CO Arg& scalar );

IN TTMA<T>& Invert();

ATT IN TTMA<T> OP*( CO TTMA<T>& mat ) CO NE;
ATT IN TOMA<T> OP*( CO TOMA<T>& mat ) CO NE;
IN TTMA<T> OP/( CO TTMA<T>& mat ) CO;
IN CE TTMA<T> Square() CO NE;


IN CE CO T& GetEntry( CRUI y , CRUI x ) CO NE;
IN CE T& RefEntry( CRUI y , CRUI x ) NE;

};

TE <TY T> IN TTMA<T> OP+( CO TTMA<T>& mat1 , CO TTMA<T>& mat2 ) NE;
TE <TY T> IN TTMA<T> OP-( CO TTMA<T>& mat1 , CO TTMA<T>& mat2 ) NE;
TE <TY T> IN CE TTMA<T> OP*( CO T& scalar , CO TTMA<T>& mat ) NE;
TE <TY T , SFINAE_FOR_MA( = nullptr )> IN CE TTMA<T> OP*( CO Arg& scalar , CO TTMA<T>& mat ) NE;
TE <TY T> IN CE TTMA<T> OP*( CO TTMA<T>& mat , CO T& scalar ) NE;
TE <TY T , SFINAE_FOR_MA( = nullptr )> IN CE TTMA<T> OP*( CO TTMA<T>& mat , CO T& scalar ) NE;
TE <TY T> IN TTMA<T> OP/( CO TTMA<T>& mat , CO T& scalar );
TE <TY T , SFINAE_FOR_MA( = nullptr )> IN TTMA<T> OP/( CO TTMA<T>& mat , CO Arg& scalar );
TE <TY T> IN TTMA<T> OP%( CO TTMA<T>& mat , CO T& scalar );
TE <TY T , SFINAE_FOR_MA( = nullptr )> IN TTMA<T> OP%( CO TTMA<T>& mat , CO Arg& scalar );



TE <TY T> IN CE TTMA<T> Square( CO TTMA<T>& mat ) NE;


TE <TY T> IN 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> IN 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> IN 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()> IN CE TTMA<T>::TTMA( CO Arg& n ) NE : TTMA( T( n ) ) {}
TE <TY T> IN 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> IN 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> IN 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> IN 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> IN 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()> IN 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()> IN 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()> IN 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> IN 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> IN CE CO 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> IN 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> IN CE TTMA<T> OP*( CO T& scalar , CO TTMA<T>& mat ) NE { RE MO( TTMA<T>( mat ) *= scalar ); }
TE <TY T , SFINAE_FOR_MA()> IN CE TTMA<T> OP*( CO Arg& scalar , CO TTMA<T>& mat ) NE { RE T( scalar ) * mat; }
TE <TY T> IN CE TTMA<T> OP*( CO TTMA<T>& mat , CO T& scalar ) NE { RE MO( TTMA<T>( mat ) *= scalar ); }
TE <TY T , SFINAE_FOR_MA()> IN 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> IN CE TTMA<T> Square( CO TTMA<T>& mat ) NE { RE mat.Square(); }


TE <TY T> IN CE TOMA<T>::TOMA( CO T& M0 , CO T& M1 ) NE : m_M0( M0 ) , m_M1( M1 ) {}
TE <TY T> IN CE TOMA<T>::TOMA( T&& M0 , T&& M1 ) NE : m_M0( MO( M0 ) ) , m_M1( MO( M1 ) ) {}
TE <TY T> IN CE TOMA<T>::TOMA( CO TOMA<T>& mat ) NE : m_M0( mat.m_M0 ) , m_M1( mat.m_M1 ) {}
TE <TY T> IN CE TOMA<T>::TOMA( TOMA<T>&& mat ) NE : m_M0( MO( mat.m_M0 ) ) , m_M1( MO( mat.m_M1 ) ) {}

TE <TY T> IN 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> IN 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> IN 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 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> IN 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()> IN 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()> IN 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()> IN CE TOMA<T>& TOMA<T>::OP%=( CO Arg& scalar ) { RE OP%=( T( scalar ) ); }

TE <TY T> IN CE CO T& TOMA<T>::GetEntry( CRUI y ) CO NE { RE y == 0 ? m_M0 : m_M1; }
TE <TY T> IN CE T& TOMA<T>::RefEntry( CRUI y ) NE { RE y == 0 ? m_M0 : m_M1; }


VEISATION_FOR_TTMA_FOR_MOD( P );


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_PW{ c1 }; FOREQ( d , 1 , fold ){ Ntd[d] = ( Nt_PW *= 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 ) }; VE<uint> ( &TheAtsu_coef_deg )[4] = TheAtsu_coef[deg]; VE<uint> ( &TheAtsu_degree_deg )[4] = TheAtsu_degree[deg]; FOR( i , 0 , 4 ){ MNP& diff_deg_i = *p_diff_deg[i]; VE<uint>& TheAtsu_coef_deg_i = TheAtsu_coef_deg[i]; VE<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 ) : MO( ( ( Twice( Nt1 ) -= k_start_1 ) += c1 ) *= MNP::DeRP( k_start >> 1 ) ) : MO( ( ( 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 );
ATT int main()
{
UNTIE;
CEXPR( uint , bound_T , 100000 );
CIN_ASSERT( T , 1 , bound_T );

SET_CEXPR( 0 );
SET_CEXPR( 1 );
SET_CEXPR( 2 );
CE MNP c2_neg{ MNP::DeRP( P - 2 ) };
CE MNP c2_inv{ MNP::DeRP( ( P + 1 ) / 2 ) };
CE MNP c2_inv_neg{ MNP::DeRP( ( P - 1 ) / 2 ) };
CO MNPN& zero = MNPN::zero();
CO MNPN one{ 0 , c1 };
CO MNPN two{ 0 , c2 };
CO MNPN two_inv{ 0 , c2_inv };
CE TOMA<MNP> v{ MNP::DeRP( 1 ) , MNP::DeRP( 0 ) };
TTMA<MNPNK> MNk_shift
{ MO( MNPNK( 1 , MNPN( 0 , c2_neg ) ) += MNPNK( 0 , MNPN( 1 , c2 ) ) ) , MO( MNPNK( 2 , MNPN( 0 , c2_inv_neg ) ) += MNPNK( 1 , MO( MNPN( 1 , c1 ) += c2_inv ) ) ) ,
MNPNK( 0 , one ) , MNPNK( 0 , zero ) };
LI<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( MO( MNk_shift ) );
VE<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++;
VE<MNPN>& comb_deg = comb[deg];
comb_deg = VE<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;
}
}
CE PW_CE<MNP,deg_lim> fp{ fold };
MNPN fp1[deg_lim];
FOREQ( deg , 0 , deg_max ){
fp1[deg] = MNPN( 0 , fp.m_val[deg] );
}
VE<VE<MNPN> > comb_fp{};
comb_fp.reserve( deg_lim );
comb_fp.push_back( VE<MNPN>() );
FOR( ddeg , 1 , deg_lim ){
VE<MNPN>& comb_ddeg = comb[ddeg];
comb_fp.push_back( VE<MNPN>() );
VE<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] );
CRUI SZ = prod_curr_i.SZ();
FOR( ddeg , 1 , SZ ){
VE<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];
}
}
}
}


CEXPR( uint , coef_SZ_max , 33 );

uint coef[deg_lim][4][coef_SZ_max];
uint coef_SZ[deg_lim][4] = {};
map<uint,uint> coef_LI{};
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_SZ_max] = coef[deg];
uint ( &coef_SZ_deg )[4] = coef_SZ[deg];
FOR( i , 0 , 4 ){
MNPN& diff_deg_i = *( p_diff_deg[i] );
CRUI SZ = diff_deg_i.SZ();
uint ( &coef_deg_i )[coef_SZ_max] = coef_deg[i];
uint& coef_SZ_deg_i = coef_SZ_deg[i];
FOR( d , 0 , SZ ){
CRUI diff_deg_i_d = diff_deg_i[d].RP();
coef_deg_i[coef_SZ_deg_i++] = diff_deg_i_d;
if( diff_deg_i_d > 0 ){
coef_LI[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--;
}
}

CEXPR( uint , coef_LI_SZ , 2176 );

MNP coef_array[coef_LI_SZ];
uint coef_array_SZ = 0;
FOR_IT( coef_LI , IT , EN ){
coef_array[IT->second = coef_array_SZ++] = MNP::DeRP( IT->first );
}


VE<uint> TheAtsu_coef[deg_lim][4] = {};
VE<uint> TheAtsu_degree[deg_lim][4] = {};
FOREQ( deg , 0 , deg_max ){
uint ( &coef_deg )[4][coef_SZ_max] = coef[deg];
uint ( &coef_SZ_deg )[4] = coef_SZ[deg];
VE<uint> ( &TheAtsu_coef_deg )[4] = TheAtsu_coef[deg];
VE<uint> ( &TheAtsu_degree_deg )[4] = TheAtsu_degree[deg];
FOR( i , 0 , 4 ){
uint ( &coef_deg_i )[coef_SZ_max] = coef_deg[i];
uint& coef_SZ_deg_i = coef_SZ_deg[i];
VE<uint>& TheAtsu_coef_deg_i = TheAtsu_coef_deg[i];
VE<uint>& TheAtsu_degree_deg_i = TheAtsu_degree_deg[i];
TheAtsu_coef_deg_i.reserve( coef_SZ_deg_i );
TheAtsu_degree_deg_i.reserve( coef_SZ_deg_i );
FOR( d , 0 , coef_SZ_deg_i ){
uint& coef_deg_i_d = coef_deg_i[d];
if( coef_deg_i_d != 0 ){
TheAtsu_coef_deg_i.push_back( coef_LI[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;
}
}
}
RE 0;
}