// 設定２のデバッグ（これはサンプルすら通らないが、どこからバグっているかを特定するための提出） #pragma GCC optimize ( "O3" ) #pragma GCC target ( "avx" ) #include using namespace std; using uint = unsigned int;using ll = long long; #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) 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 GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #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 QUIT RE 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define RETURN( ANSWER ) COUT( ANSWER ); QUIT #define TE template #define TY typename #define PU public #define PR PU #define IN inline #define OP operator #define CE constexpr #define CO const #define RE return #define NE noexcept #define WH while #define VE vector #define LI list #define RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE OP=( zero ); } #define RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE TP( m_N ); } #define SET_VE_FOR_ANSWER_OF_MU_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) if( PO::m_size < N_OUTPUT_LIM ){ for( uint i = PO::m_size ; i < N_OUTPUT_LIM ; i++ ){ PO::m_f.push_back( 0 ); } PO::m_size = N_OUTPUT_LIM; } #define SET_VE_FOR_ANSWER_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) VE answer( N_OUTPUT_LIM ) #define SET_SUM_OF_MU_FOR_TRUNCATED_POLYNOMIAL PO::m_f[i] = sum #define SET_SUM_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL answer[i] = sum #define SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_START_NUM ) uint N_INPUT_START_NUM; for( uint i = 0 ; i < SIZE && searching ; i++ ){ if( F[i] != zero ){ N_INPUT_START_NUM = i; searching = false; } } #define SET_N_INPUT_MAX_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_MAX_NUM ) uint N_INPUT_MAX_NUM; searching = true; for( uint i = ( SIZE ) - 1 ; searching ; i-- ){ if( F[i] != zero ){ N_INPUT_MAX_NUM = i; searching = false; } } #define CONVOLUTION_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; T sum{ zero }; for( uint j = J_MIN ; j <= j_max ; j++ ){ sum += PO::m_f[j] * f.PO::m_f[i - j]; } PO::m_f[i] = sum; #define CONVOLUTION_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; T& m_fi = answer[i]; for( uint j = J_MIN ; j <= j_max ; j++ ){ m_fi += PO::m_f[j] * f.PO::m_f[i - j]; } #define ZEROIFICATION_FOR_MU_FOR_TRUNCATED_POLYNOMIAL for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ PO::m_f[i] = 0; } #define ZEROIFICATION_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ answer[i] = 0; } #define CN( S1 , S2 ) SUBSTITUTE_CN( S1 , S2 ) #define SUBSTITUTE_CN( S1 , S2 ) S1 ## S2 #define DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MU , ACCESS_ENTRY ) CN( CN( RETURN_ZERO_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( PO::m_size == 0 ); uint N_output_max = PO::m_size + f.PO::m_size - 2; if( N_output_max >= m_N ){ N_output_max = m_N - 1; } CO uint N_output_lim = N_output_max + 1; CN( CN( SET_VE_FOR_ANSWER_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim ); for( uint i = N_output_max ; searching ; i-- ){ T sum{ zero }; for( uint j = 0 ; j <= i ; j++ ){ sum += ACCESS_ENTRY * f.PO::OP[]( i - j ); } CN( CN( SET_SUM_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL ); searching = i > 0; } #define DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MU , PO::m_f[j] ) #define DEFINITION_0_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO , PO::OP[]( j ) ) #define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( PO::m_f , PO::m_size , N_input_start_0 ); CN( CN( RETURN_ZERO_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( f , f.PO::m_size , N_input_start_1 ); #define DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) #define DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO ) #define DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL SET_N_INPUT_MAX_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( PO::m_f , PO::m_size , N_input_max_0 ); SET_N_INPUT_MAX_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( f , f.PO::m_size < m_N ? f.PO::m_size : m_N , N_input_max_1 ); CO uint N_input_max_0_max_1 = N_input_max_0 + N_input_max_1; CO uint N_input_start_0_start_1 = N_input_start_0 + N_input_start_1; #define DEFINITION_2_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL #define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) CO uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1; CO uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1; CO uint N_output_max_fixed = N_output_lim_fixed - 1; CN( CN( SET_VE_FOR_ANSWER_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim_fixed ); for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){ CN( CN( CONVOLUTION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( i - N_input_max_1 ); } searching = true; for( uint i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1 : N_output_max_fixed ; searching ; i-- ){ CN( CN( CONVOLUTION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_input_start_0 ); searching = i > N_input_start_0_start_1; } CN( CN( ZEROIFICATION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL ); #define DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) #define DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO ) #define DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL uint two_power = FFT_MU_border_1_2; uint exponent = FFT_MU_border_1_2_exponent; T two_power_inv{ FFT_MU_border_1_2_inv }; WH( N_input_truncated_deg_0_deg_1 >= two_power ){ two_power *= 2; two_power_inv /= 2; exponent++; } VE f0{ move( FFT( PO::m_f , N_input_start_0 , N_input_max_0 + 1 , 0 , two_power , exponent ) ) }; CO VE f1{ move( FFT( f.PO::m_f , N_input_start_1 , N_input_max_1 + 1 , 0 , two_power , exponent ) ) }; for( uint i = 0 ; i < two_power ; i++ ){ f0[i] *= f1[i]; } #define DEFINITION_4_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL #define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TP< TYPE > f_inv{ power_2 , PO< TYPE >::CO_one() / f[0] }; WH( power_2 < N ){ power = power_2; power_2 *= 2; f_inv.SetTruncation( power_2 ); RECURSION; } f_inv.SetTruncation( N ); RE f_inv #define DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TP< TYPE > f_exp{ power_2 , PO< TYPE >::CO_one() }; WH( power_2 < N ){ power = power_2; power_2 *= 2; f_exp.SetTruncation( power_2 ); RECURSION; } f_exp.SetTruncation( N ); RE f_exp #define DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TRUNCATED_POLYNOMIAL( TYPE , BORDER_0 , BORDER_1 , BORDER_1_2 , BORDER_1_2_EXPONENT , BORDER_1_2_INV ) TE <> CE CO uint FFT_MU_border_0< TYPE > = BORDER_0; TE <> CE CO uint FFT_MU_border_1< TYPE > = BORDER_1; TE <> CE CO uint FFT_MU_border_1_2< TYPE > = BORDER_1_2; TE <> CE CO uint FFT_MU_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> CE CO uint FFT_MU_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TP< TYPE >& TP< TYPE >::OP*=( CO PO< TYPE >& f ) { RE TP< TYPE >::FFT_MU( f ); } TE <> TP< TYPE > Inverse( CO TP< TYPE >& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_inv.TruncatedMinus( f_inv.FFT_TruncatedMU_CO( f , power , power_2 ).FFT_TruncatedMU( f_inv , power , power_2 ) , power , power_2 ) ); } TE <> TP< TYPE > Exp( CO TP< TYPE >& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).FFT_TruncatedMU_CO( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).FFT_TruncatedMU( f_exp , power , power_2 ) , power , power_2 ) ); } TE IN T Residue( CO T& a , CO T& p ){ RE a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }TE class Mod{protected:ll m_n;ll m_inv;PU:IN Mod() NE;IN Mod( CO ll& n ) NE;IN Mod( CO Mod& n ) NE;IN Mod& OP=( CO ll& n ) NE;Mod& OP=( CO Mod& n ) NE;Mod& OP+=( CO ll& n ) NE;IN Mod& OP+=( CO Mod& n ) NE;IN Mod& OP-=( CO ll& n ) NE;IN Mod& OP-=( CO Mod& n ) NE;Mod& OP*=( CO ll& n ) NE;Mod& OP*=( CO Mod& n ) NE;virtual Mod& OP/=( CO ll& n );virtual Mod& OP/=( CO Mod& n );Mod& OP%=( CO ll& n );IN Mod& OP%=( CO Mod& n );IN Mod OP-() CO NE;IN Mod& OP++() NE;IN Mod& OP++( int ) NE;IN Mod& OP--() NE;IN Mod& OP--( int ) NE;IN CO ll& Represent() CO NE;void Invert() NE;bool CheckInvertible() NE;bool IsSmallerThan( CO ll& n ) CO NE;bool IsBiggerThan( CO ll& n ) CO NE;};TE IN bool OP==( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP==( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP==( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP==( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP!=( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP!=( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP!=( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP!=( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP<( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP<( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP<( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP<=( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP<=( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP<=( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP<=( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP>( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP>( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP>( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP>( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP>=( CO Mod& n0 , CO ll& n1 ) NE;TE IN bool OP>=( CO ll& n0 , CO Mod& n1 ) NE;TE IN bool OP>=( CO Mod& n0 , CO Mod& n1 ) NE;TE IN bool OP>=( CO Mod& n0 , CO Mod& n1 ) NE;TE Mod OP+( CO Mod& n0 , CO ll& n1 ) NE;TE Mod OP+( CO ll& n0 , CO Mod& n1 ) NE;TE Mod OP+( CO Mod& n0 , CO Mod& n1 ) NE;TE IN Mod OP-( CO Mod& n0 , CO ll& n1 ) NE;TE Mod OP-( CO ll& n0 , CO Mod& n1 ) NE;TE Mod OP-( CO Mod& n0 , CO Mod& n1 ) NE;TE Mod OP*( CO Mod& n0 , CO ll& n1 ) NE;TE Mod OP*( CO ll& n0 , CO Mod& n1 ) NE;TE Mod OP*( CO Mod& n0 , CO Mod& n1 ) NE;TE Mod OP/( CO Mod& n0 , CO ll& n1 );TE Mod OP/( CO ll& n0 , CO Mod& n1 );TE Mod OP/( CO Mod& n0 , CO Mod& n1 );TE Mod OP%( CO Mod& n0 , CO ll& n1 );TE IN Mod OP%( CO ll& n0 , CO Mod& n1 );TE IN Mod OP%( CO Mod& n0 , CO Mod& n1 );TE Mod Inverse( CO Mod& n );TE Mod Power( CO Mod& n , CO ll& p , CO string& method = "normal" );TE <> IN Mod<2> Power( CO Mod<2>& n , CO ll& p , CO string& method );TE IN Mod Power( CO Mod& n , CO Mod& p , CO string& method = "normal" );TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method );TE IN T Square( CO T& t );TE <> IN Mod<2> Square >( CO Mod<2>& t );TE IN string to_string( CO Mod& n ) NE;TE IN basic_ostream& OP<<( basic_ostream& os , CO Mod& n );void LazyEvaluationOfModularInverse( CO ll& M , CO ll& n , ll& m ){CE CO ll border = 1000000;if( n > border ){CO ll n_minus = M - n;if( n_minus <= border ){LazyEvaluationOfModularInverse( M , n_minus , m );m = M - m;return;} else {m = 1;ll exponent = M - 2;ll power_n = n;WH( exponent != 0 ){if( exponent % 2 == 1 ){( m *= power_n ) %= M;}( power_n *= power_n ) %= M;exponent /= 2;}return;}}static LI memory_M{};static LI > memory_inverse{};auto itr_M = memory_M.begin() , end_M = memory_M.end();auto itr_inverse = memory_inverse.begin();VE* p_inverse = nullptr;WH( itr_M != end_M && p_inverse == nullptr ){if( *itr_M == M ){p_inverse = &( *itr_inverse );}itr_M++;itr_inverse++;}if( p_inverse == nullptr ){memory_M.push_front( M );memory_inverse.push_front( VE() );p_inverse = &( memory_inverse.front() );p_inverse->push_back( M );}CO ll size = p_inverse->size();for( ll i = size ; i <= n ; i++ ){p_inverse->push_back( 0 );}ll& n_inv = ( *p_inverse )[n];if( n_inv != 0 ){m = n_inv;return;}CO ll M_abs = M >= 0 ? M : -M;CO ll n_sub = M_abs % n;ll n_sub_inv = ( *p_inverse )[n_sub];if( n_sub_inv == 0 ){LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv );}if( n_sub_inv != M ){n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs );m = n_inv;return;}for( ll i = 1 ; i < M_abs ; i++ ){if( ( n * i ) % M_abs == 1 ){n_inv = i;m = n_inv;return;}}n_inv = M;m = n_inv;return;}TE IN Mod::Mod() NE : m_n( 0 ) , m_inv( M ){}TE IN Mod::Mod( CO ll& n ) NE : m_n( Residue( n , M ) ) , m_inv( 0 ){}TE IN Mod::Mod( CO Mod& n ) NE : m_n( n.m_n ) , m_inv( 0 ){}TE IN Mod& Mod::OP=( CO ll& n ) NE { RE OP=( Mod( n ) ); }TE Mod& Mod::OP=( CO Mod& n ) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE Mod& Mod::OP+=( CO ll& n ) NE{m_n = Residue( m_n + n , M );m_inv = 0;RE *this;}TE IN Mod& Mod::OP+=( CO Mod& n ) NE { RE OP+=( n.m_n ); };TE IN Mod& Mod::OP-=( CO ll& n ) NE { RE OP+=( -n ); }TE IN Mod& Mod::OP-=( CO Mod& n ) NE { RE OP-=( n.m_n ); }TE Mod& Mod::OP*=( CO ll& n ) NE{m_n = Residue( m_n * n , M );m_inv = 0;RE *this;}TE Mod& Mod::OP*=( CO Mod& n ) NE{m_n = Residue( m_n * n.m_n , M );if( m_inv == 0 || n.m_inv == 0 ){m_inv = 0;} else if( m_inv == M || n.m_inv == M ){m_inv = M;} else {Residue( m_inv * n.m_inv , M );}RE *this;}TE Mod& Mod::OP/=( CO ll& n ){RE OP/=( Mod( n ) );}TE Mod& Mod::OP/=( CO Mod& n ){RE OP*=( Inverse( n ) );}TE Mod& Mod::OP%=( CO ll& n ){m_n %= Residue( n , M );m_inv = 0;RE *this;}TE IN Mod& Mod::OP%=( CO Mod& n ) { RE OP%=( n.m_n ); }TE IN Mod Mod::OP-() CO NE { RE Mod( 0 ).OP-=( *this ); }TE IN Mod& Mod::OP++() NE { RE OP+=( 1 ); }TE IN Mod& Mod::OP++( int ) NE { RE OP++(); }TE IN Mod& Mod::OP--() NE { RE OP-=( 1 ); }TE IN Mod& Mod::OP--( int ) NE { RE OP-=(); }TE IN CO ll& Mod::Represent() CO NE { RE m_n; }TE void Mod::Invert() NE{if( CheckInvertible() ){ll i = m_inv;m_inv = m_n;m_n = i;} else {m_n = M;m_inv = M;}return;}TE bool Mod::CheckInvertible() NE{if( m_inv == 0 ){LazyEvaluationOfModularInverse( M , m_n , m_inv );}RE m_inv != M;}TE IN bool Mod::IsSmallerThan( CO ll& n ) CO NE { RE m_n < Residue( n , M ); }TE IN bool Mod::IsBiggerThan( CO ll& n ) CO NE { RE m_n > Residue( n , M ); }TE IN bool OP==( CO Mod& n0 , CO ll& n1 ) NE { RE n0 == Mod( n1 ); }TE IN bool OP==( CO ll& n0 , CO Mod& n1 ) NE { RE Mod( n0 ) == n0; }TE IN bool OP==( CO Mod& n0 , CO Mod& n1 ) NE { RE n0.Represent() == n1.Represent(); }TE IN bool OP!=( CO Mod& n0 , CO ll& n1 ) NE { RE !( n0 == n1 ); }TE IN bool OP!=( CO ll& n0 , CO Mod& n1 ) NE { RE !( n0 == n1 ); }TE IN bool OP!=( CO Mod& n0 , CO Mod& n1 ) NE { RE !( n0 == n1 ); }TE IN bool OP<( CO Mod& n0 , CO ll& n1 ) NE { RE n0.IsSmallerThan( n1 ); }TE IN bool OP<( CO ll& n0 , CO Mod& n1 ) NE { RE n1.IsBiggerThan( n0 ); }TE IN bool OP<( CO Mod& n0 , CO Mod& n1 ) NE { RE n0.Represent() < n1.Represent(); }TE IN bool OP<=( CO Mod& n0 , CO ll& n1 ) NE { RE !( n1 < n0 ); }TE IN bool OP<=( CO ll& n0 , CO Mod& n1 ) NE { RE !( n1 < n0 ); }TE IN bool OP<=( CO Mod& n0 , CO Mod& n1 ) NE { RE !( n1 < n0 ); }TE IN bool OP>( CO Mod& n0 , CO ll& n1 ) NE { RE n1 < n0; }TE IN bool OP>( CO ll& n0 , CO Mod& n1 ) NE { RE n1 < n0; }TE IN bool OP>( CO Mod& n0 , CO Mod& n1 ) NE { RE n1 < n0; }TE IN bool OP>=( CO Mod& n0 , CO ll& n1 ) NE { RE !( n0 < n1 ); }TE IN bool OP>=( CO ll& n0 , CO Mod& n1 ) NE { RE !( n0 < n1 ); }TE IN bool OP>=( CO Mod& n0 , CO Mod& n1 ) NE { RE !( n0 < n1 ); }TE Mod OP+( CO Mod& n0 , CO ll& n1 ) NE{auto n = n0;n += n1;RE n;}TE IN Mod OP+( CO ll& n0 , CO Mod& n1 ) NE { RE n1 + n0; }TE IN Mod OP+( CO Mod& n0 , CO Mod& n1 ) NE { RE n0 + n1.Represent(); }TE IN Mod OP-( CO Mod& n0 , CO ll& n1 ) NE { RE n0 + ( -n1 ); }TE IN Mod OP-( CO ll& n0 , CO Mod& n1 ) NE { RE Mod( n0 - n1.Represent() ); }TE IN Mod OP-( CO Mod& n0 , CO Mod& n1 ) NE { RE n0 - n1.Represent(); }TE Mod OP*( CO Mod& n0 , CO ll& n1 ) NE{auto n = n0;n *= n1;RE n;}TE IN Mod OP*( CO ll& n0 , CO Mod& n1 ) NE { RE n1 * n0; }TE Mod OP*( CO Mod& n0 , CO Mod& n1 ) NE{auto n = n0;n *= n1;RE n;}TE IN Mod OP/( CO Mod& n0 , CO ll& n1 ) { RE n0 / Mod( n1 ); }TE IN Mod OP/( CO ll& n0 , CO Mod& n1 ) { RE Mod( n0 ) / n1; }TE Mod OP/( CO Mod& n0 , CO Mod& n1 ){auto n = n0;n /= n1;RE n;}TE Mod OP%( CO Mod& n0 , CO ll& n1 ){auto n = n0;n %= n1;RE n;}TE IN Mod OP%( CO ll& n0 , CO Mod& n1 ) { RE Mod( n0 ) % n1.Represent(); }TE IN Mod OP%( CO Mod& n0 , CO Mod& n1 ) { RE n0 % n1.Represent(); }TE Mod Inverse( CO Mod& n ){auto n_copy = n;n_copy.Invert();RE n_copy;}TE Mod Power( CO Mod& n , CO ll& p , CO string& method ){if( p >= 0 ){RE Power,ll>( n , p , 1 , true , true , method );}RE Inverse( Power( n , -p , method ) );}TE <> IN Mod<2> Power( CO Mod<2>& n , CO ll& p , CO string& method ) { RE p == 0 ? 1 : n; }TE IN Mod Power( CO Mod& n , CO Mod& p , CO string& method ) { RE Power,ll>( n , p.Represent() , method ); }TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method ) { RE p == 0 ? 1 : n; }TE <> IN Mod<2> Square >( CO Mod<2>& t ) { RE t; }TE IN string to_string( CO Mod& n ) NE { RE to_string( n.Represent() ) + " + MZ"; }TE IN basic_ostream& OP<<( basic_ostream& os , CO Mod& n ) { RE os << n.Represent(); } IN CEXPR( ll , P , 998244353 );TE class TP;TE class PO{friend class TP;protected:VE m_f;uint m_size;bool m_no_redundant_zero;PU:IN PO();IN PO( CO T& t );IN PO( CO PO& f );IN PO( PO&& f );IN PO( CO uint& i , CO T& t );IN PO( VE&& f );PO& OP=( CO T& t );PO& OP=( CO PO& f );IN CO T& OP[]( CO uint& i ) CO;IN T& OP[]( CO uint& i );IN T OP()( CO T& t ) CO;IN PO& OP+=( CO T& t );PO& OP+=( CO PO& f );IN PO& OP-=( CO T& t );PO& OP-=( CO PO& f );PO& OP*=( CO T& t );PO& OP*=( CO PO& f );PO& OP/=( CO T& t );PO& OP/=( CO PO& f );PO& OP%=( CO T& t );PO& OP%=( CO PO& f );IN PO OP-() CO;PO& OP<<=( CO T& t );IN CO VE& GetCoefficient() CO NE;IN CO uint& size() CO NE;void RemoveRedundantZero();IN string Display() CO NE;static IN CO PO& zero();static IN CO T& CO_zero();static IN CO T& CO_one();static IN CO T& CO_minus_one();};TE bool OP==( CO PO& f0 , CO T& t1 );TE bool OP==( CO PO& f0 , CO PO& f1 );TE IN bool OP!=( CO PO& f0 , CO P& f1 );TE IN PO OP+( CO PO& f0 , CO P& f1 );TE IN PO OP-( CO PO& f );TE IN PO OP-( CO PO& f0 , CO P& f1 );TE IN PO OP*( CO PO& f0 , CO P& f1 );TE IN PO OP/( CO PO& f0 , CO P& f1 );TE IN PO OP%( CO PO& f0 , CO P& f1 );TE IN PO OP<<( CO PO& f , CO T& t );TE IN LI >& Prod( LI >& f );TE class TP;TE TP TruncatedDifferential( CO TP& f , CO uint& N_output_start_plus_one );TE TP TruncatedIntegral( CO TP& f , CO uint& N_output_start );TE class TP;TE TP TruncatedDifferential( CO TP& f , CO uint& N_output_start_plus_one );TE TP TruncatedIntegral( CO TP& f , CO uint& N_output_start );TE class TP :PU PO{friend TP TruncatedDifferential( CO TP& f , CO uint& N_output_start_plus_one );friend TP TruncatedIntegral( CO TP& f , CO uint& N_output_start );PR:uint m_N;PU:IN TP( CO uint& N = 0 );IN TP( CO TP& f );IN TP( CO uint& N , CO T& t );TP( CO uint& N , CO PO& f );IN TP( CO uint& N , PO&& f );IN TP( CO uint& N , CO uint& i , CO T& t );IN TP( CO uint& N , VE&& f );IN TP& OP=( CO TP& f );IN TP& OP=( CO T& t );IN TP& OP=( CO PO& f );IN TP& OP+=( CO T& t );IN TP& OP+=( CO PO& f );IN TP& OP+=( CO TP& f );TP& TruncatedPlus( CO PO& f , CO uint& N_input_start , CO uint& N_input_limit );IN TP& OP-=( CO T& t );IN TP& OP-=( CO PO& f );IN TP& OP-=( CO TP& f );TP& TruncatedMinus( CO PO& f , CO uint& N_input_start , CO uint& N_input_limit );IN TP& OP*=( CO T& t );TP& OP*=( CO PO& f );TP& FFT_MU( CO PO& f );TP& TruncatedMU( CO PO& f , CO uint& N_input_start , CO uint& N_input_lim );TP& FFT_TruncatedMU( CO PO& f , CO uint& N_input_start , CO uint& N_input_lim );TP TruncatedMU_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;TP FFT_TruncatedMU_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;IN TP& OP/=( CO T& t );IN TP& OP/=( CO TP& t );IN TP& OP%=( CO T& t );IN TP OP-() CO;IN void SetTruncation( CO uint& N ) NE;IN CO uint& GetTruncation() CO NE;IN TP& TruncateInitial( CO uint& N ) NE;IN TP& TruncateFinal( CO uint& N ) NE;};TE IN CE CO uint FFT_MU_border_0;TE IN CE CO uint FFT_MU_border_1;TE IN CE CO uint FFT_MU_border_1_2;TE IN CE CO uint FFT_MU_border_1_2_exponent;TE IN CE CO uint FFT_MU_border_1_2_inv;TE IN TP OP+( CO TP& f0 , CO P& f1 );TE IN TP OP-( CO TP& f );TE IN TP OP-( CO TP& f0 , CO P& f1 );TE IN TP OP*( CO TP& f0 , CO P& f1 );TE IN TP OP/( CO TP& f0 , CO P& f1 );TE IN TP OP%( CO TP& f0 , CO T& t1 );TE IN TP Differential( CO TP& f );TE IN TP Differential( CO uint& i , CO TP& f );TE TP TruncatedDifferential( CO TP& f , CO uint& N_output_start_plus_one );TE IN TP Integral( CO TP& f );TE TP TruncatedIntegral( CO TP& f , CO uint& N_output_start );TE TP Inverse( CO TP& f );TE TP Exp( CO TP& f );TE IN TP Log( CO TP& f );TE TP Power( CO TP& f , CO T& t );TE IN TP& Prod( LI >& f , CO uint& N );TE IN PO::PO() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {}TE IN PO::PO( CO T& t ) : PO() { if( t != CO_zero() ){ OP[]( 0 ) = t; } }TE IN PO::PO( CO PO& f ) : m_f( f.m_f ) , m_size( f.m_size ) , m_no_redundant_zero( f.m_no_redundant_zero ) {}TE IN PO::PO( PO&& f ) : m_f( move( f.m_f ) ) , m_size( move( f.m_size ) ) , m_no_redundant_zero( move( f.m_no_redundant_zero ) ) {}TE IN PO::PO( CO uint& i , CO T& t ) : PO() { if( t != CO_zero() ){ OP[]( i ) = t; } }TE IN PO::PO( VE&& f ) : m_f( move( f ) ) , m_size( m_f.size() ) , m_no_redundant_zero( false ) {}TE IN PO& PO::OP=( CO T& t ) { m_f.clear(); m_size = 0; OP[]( 0 ) = t; RE *this; }TE IN PO& PO::OP=( CO PO& f ) { m_f = f.m_f; m_size = f.m_size; m_no_redundant_zero = f.m_no_redundant_zero; RE *this; }TE CO T& PO::OP[]( CO uint& i ) CO{if( m_size <= i ){RE CO_zero();}RE m_f[i];}TE IN T& PO::OP[]( CO uint& i ){m_no_redundant_zero = false;if( m_size <= i ){CO T& z = CO_zero();WH( m_size <= i ){m_f.push_back( z );m_size++;}}RE m_f[i];}TE IN T PO::OP()( CO T& t ) CO { RE ( *this % ( PO( 1 , CO_one() ) - t ) )[0]; }TE IN PO& PO::OP+=( CO T& t ) { OP[]( 0 ) += t; RE *this; }TE PO& PO::OP+=( CO PO& f ){for( uint i = 0 ; i < f.m_size ; i++ ){OP[]( i ) += f.m_f[i];}RE *this;}TE IN PO& PO::OP-=( CO T& t ) { OP[]( 0 ) -= t; RE *this; }TE PO& PO::OP-=( CO PO& f ){for( uint i = 0 ; i < f.m_size ; i++ ){OP[]( i ) -= f.m_f[i];}RE *this;}TE PO& PO::OP*=( CO T& t ){if( m_size == 0 || t == CO_one() ){RE *this;}if( t == CO_zero() ){RE OP=( zero() );}for( uint i = 0 ; i < m_size ; i++ ){OP[]( i ) *= t;}RE *this;}TE PO& PO::OP*=( CO PO& f ){if( m_size == 0 ){RE *this;}if( f.m_size == 0 ){RE OP=( zero() );}CO uint size = m_size + f.m_size - 1;PO product{}; for( uint i = 0 ; i < size ; i++ ){T& product_i = product[i];CO uint j_min = m_size <= i ? i - m_size + 1 : 0;CO uint j_lim = i < f.m_size ? i + 1 : f.m_size;for( uint j = j_min ; j < j_lim ; j++ ){product_i += m_f[i - j] * f.m_f[j];}}RE OP=( product );}TE PO& PO::OP/=( CO T& t ){if( t == CO_one() ){RE *this;}for( uint i = 0 ; i < m_size ; i++ ){OP[]( i ) /= t;}RE *this;}TE PO& PO::OP/=( CO PO& f ){if( m_size >= f.m_size ){assert( f.m_size > 0 );uint size0 = m_size - f.m_size + 1;TP f0_copy( size0 );for( uint d0 = 0 ; d0 < size0 ; d0++ ){f0_copy.PO::m_f.push_back( m_f[m_size - 1 - d0] );}f0_copy.PO::m_size = size0;f0_copy.PO::m_no_redundant_zero = false;TP f1_copy( size0 );uint size1 = size0 < f.m_size ? size0 : f.m_size;for( uint d1 = 0 ; d1 < size1 ; d1++ ){f1_copy.PO::m_f.push_back( f.m_f[f.m_size - 1 - d1] );}f1_copy.PO::m_size = size1;f1_copy.PO::m_no_redundant_zero = false;f0_copy /= f1_copy;for( uint d0 = 0 ; d0 < size0 ; d0++ ){m_f[d0] = f0_copy[ size0 - 1 - d0 ];}WH( m_size > size0 ){m_f.pop_back();m_size--;}} else {PO::m_f.clear();PO::m_size = 0;PO::m_no_redundant_zero = true;}RE *this;}TE PO& PO::OP%=( CO T& t ){if( t == CO_one() ){RE OP=( zero() );}for( uint i = 0 ; i < m_size ; i++ ){OP[]( i ) %= t;}RE *this;}TE PO& PO::OP%=( CO PO& f ){if( m_size >= f.m_size ){OP-=( TP( m_size , move( *this / f ) ) * f );RemoveRedundantZero();m_no_redundant_zero = true;}RE *this;}TE IN PO PO::OP-() CO { RE PO().OP-=( *this ); }TE PO& PO::OP<<=( CO T& t ){if( m_size > 0 ){static T factorial_curr = 1;static VE factorial = { 1 , 1 };static T factorial_inv_curr = 1;static VE factorial_inv = { 1 , 1 };uint size = factorial.size();WH( size < m_size ){factorial.push_back( factorial_curr *= size );factorial_inv.push_back( factorial_inv_curr /= size );size++;}for( uint d = 0 ; d < m_size ; d++ ){m_f[d] *= factorial[d];}TP f{ m_size * 2 };T power_t = CO_one();for( uint d = 0 ; d < m_size ; d++ ){f[m_size - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for( uint d = 0 ; d < m_size ; d++ ){m_f[d] = f.PO::m_f[d + m_size - 1] * factorial_inv[d];}}RE *this;}TE IN CO VE& PO::GetCoefficient() CO NE { RE m_f; }TE IN CO uint& PO::size() CO NE { RE m_size; }TE void PO::RemoveRedundantZero(){if( m_no_redundant_zero ){return;}CO T& z = CO_zero();WH( m_size > 0 ? m_f[m_size - 1] == z : false ){m_f.pop_back();m_size--;}m_no_redundant_zero = true;return;}TE string PO::Display() CO NE{string s = "(";if( m_size > 0 ){s += to_string( m_f[0] );for( uint i = 1 ; i < m_size ; i++ ){s += ", " + to_string( m_f[i] );}}s += ")";RE s;}TE IN CO PO& PO::zero() { static CO PO z{}; RE z; }TE IN CO T& PO::CO_zero() { static CO T z{ 0 }; RE z; }TE IN CO T& PO::CO_one() { static CO T o{ 1 }; RE o; }TE IN CO T& PO::CO_minus_one() { static CO T m{ -1 }; RE m; }TE bool OP==( CO PO& f0 , CO T& t1 ){CO uint& size = f0.size();CO T& zero = PO::CO_zero();for( uint i = 1 ; i < size ; i++ ){if( f0[i] != zero ){RE false;}}RE f0[0] == t1;}TE bool OP==( CO PO& f0 , CO PO& f1 ){CO uint& size0 = f0.size();CO uint& size1 = f1.size();CO uint& size = size0 < size1 ? size1 : size0;for( uint i = 0 ; i < size ; i++ ){if( f0[i] != f1[i] ){RE false;}}RE true;}TE IN bool OP!=( CO PO& f0 , CO P& f1 ) { RE !( f0 == f1 ); }TE IN PO OP+( CO PO& f0 , CO P& f1 ) { PO f = f0; f += f1; RE f; }TE IN PO OP-( CO PO& f ) { RE PO::zero() - f; }TE IN PO OP-( CO PO& f0 , CO P& f1 ) { PO f = f0; RE f.OP-=( f1 ); }TE IN PO OP*( CO PO& f0 , CO P& f1 ) { PO f = f0; RE f.OP*=( f1 ); }TE IN PO OP/( CO PO& f0 , CO P& f1 ) { PO f = f0; RE f.OP/=( f1 ); }TE IN PO OP%( CO PO& f0 , CO P& f1 ) { PO f = f0; RE f.OP%=( f1 ); }TE PO OP<<( CO PO& f , CO T& t ) { RE PO( f ) <<= t; };TE IN PO& Prod( LI >& f ){if( f.empty() ){f.push_back( PO::CO_one() );}if( f.size() == 1 ){RE f.front();}auto itr = f.begin() , end = f.end();WH( itr != end ){PO& t = *itr;itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod( f );}TE IN CE CO uint LimitOfPowerForFFT;TE IN CE CO uint BorderForFFT;TE IN CO T ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT];TE IN CO T ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT];TE IN VE FFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO uint& exponent );TE IN VE FFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO uint& exponent );TE VE IFFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO T& two_power_inv , CO uint& exponent );TE VE IFFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO T& two_power_inv , CO uint& exponent );TE <> IN CE CO uint LimitOfPowerForFFT > = 24;TE <> IN CE CO uint BorderForFFT > = 4; TE <> IN CO Mod

( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT >]{static CO Mod

PRT[ LimitOfPowerForFFT > ] ={Mod

( 1 ) ,Mod

( 998244352 ) ,Mod

( 911660635 ) ,Mod

( 625715529 ) ,Mod

( 373294451 ) ,Mod

( 827987769 ) ,Mod

( 280333251 ) ,Mod

( 581015842 ) ,Mod

( 628092333 ) ,Mod

( 300892551 ) ,Mod

( 586046298 ) ,Mod

( 615001099 ) ,Mod

( 318017948 ) ,Mod

( 64341522 ) ,Mod

( 106061068 ) ,Mod

( 304605202 ) ,Mod

( 631920086 ) ,Mod

( 857779016 ) ,Mod

( 841431251 ) ,Mod

( 805775211 ) ,Mod

( 390359979 ) ,Mod

( 923521 ) ,Mod

( 961 ) ,Mod

( 31 )};RE PRT;}TE <> IN CO Mod

( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT >]{static CO Mod

PRT[ LimitOfPowerForFFT > ] ={Mod

( 1 ) ,Mod

( 998244352 ) ,Mod

( 86583718 ) ,Mod

( 488723995 ) ,Mod

( 369330050 ) ,Mod

( 543653592 ) ,Mod

( 382946991 ) ,Mod

( 844956623 ) ,Mod

( 91420391 ) ,Mod

( 433414612 ) ,Mod

( 288894979 ) ,Mod

( 260490556 ) ,Mod

( 857007890 ) ,Mod

( 736054570 ) ,Mod

( 474649464 ) ,Mod

( 948509906 ) ,Mod

( 114942468 ) ,Mod

( 962405921 ) ,Mod

( 667573957 ) ,Mod

( 46809892 ) ,Mod

( 304321983 ) ,Mod

( 30429817 ) ,Mod

( 293967900 ) ,Mod

( 128805723 )};RE PRT;}TE static VE FFT_Body( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO uint& exponent , CO T ( &PRT )[LimitOfPowerForFFT] );TE static VE FFT_Body( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO uint& exponent , CO uint& start , CO uint& depth , CO T ( &PRT )[LimitOfPowerForFFT] );TE IN VE FFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO uint& exponent ) { RE FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , 0 , 1 , PrimitiveRootOfTwoForFFT() ); }TE IN VE FFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO uint& exponent ) { RE FFT_Body( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , PrimitiveRootOfTwoForFFT() ); }TE VE IFFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO T& two_power_inv , CO uint& exponent ){VE answer{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT() ) ) };CO uint size = answer.size();for( uint i = 0 ; i < size ; i++ ){answer[i] *= two_power_inv;}RE answer;}TE VE IFFT( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO T& two_power_inv , CO uint& exponent ){VE answer{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT() ) ) };uint size = answer.size();CO uint N_output_length = N_output_lim - N_output_start + N_output_shift;if( size < N_output_length ){size = N_output_length;}for( uint i = N_output_shift ; i < size ; i++ ){answer[i] *= two_power_inv;}RE answer;}TE static VE FFT_Body( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& N_output_start , CO uint& N_output_lim , CO uint& N_output_shift , CO uint& two_power , CO uint& exponent , CO T ( &PRT )[LimitOfPowerForFFT] ){CO uint length = N_output_lim - N_output_start + N_output_shift;VE answer( length );if( two_power == 1 ){if( N_input_shift == 0 && N_output_shift < length ){if( N_input_start < N_input_lim ){answer[N_output_shift] = f[N_input_start];}}} else {CO T& zeta = PRT[exponent];T zeta_power = PRT[0];uint N_output_start_copy = N_output_start;uint digit = 0;if( N_output_start_copy != 0 ){if( N_output_start_copy % 2 == 1 ){zeta_power *= zeta;}N_output_start_copy /= 2;digit++;}WH( N_output_start_copy != 0 ){if( N_output_start_copy % 2 == 1 ){zeta_power *= PRT[exponent - digit];}N_output_start_copy /= 2;digit++;}CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;VE answer_sub0{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , 0 , 2 , PRT ) ) };VE answer_sub1{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , 1 , 2 , PRT ) ) };for( uint i = N_output_start ; i < N_output_lim ; i++ ){CO uint i_sub = i % two_power_sub;answer[i - N_output_start + N_output_shift] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];zeta_power *= zeta;}}RE answer;}TE static VE FFT_Body( CO VE& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO uint& exponent , CO uint& start , CO uint& depth , CO T ( &PRT )[LimitOfPowerForFFT] ){VE answer( two_power );CO uint start_depth = start + ( ( two_power - 1 ) * depth );CO uint N_input_length = N_input_lim - N_input_start + N_input_shift;if( start < N_input_length && N_input_shift <= start_depth ){uint j_min;if( start < N_input_shift ){CO uint N_input_shift_shift = N_input_shift - start;j_min = N_input_shift_shift / depth + ( N_input_shift_shift % depth == 0 ? 0 : 1 );} else {j_min = 0;}uint j_lim;if( N_input_length <= start_depth ){CO uint N_input_length_shift = N_input_length - start;j_lim = N_input_length_shift / depth + ( N_input_length_shift % depth == 0 ? 0 : 1 );} else {j_lim = two_power;}CO T zero{ 0 };uint count = 0;uint index_hit;uint j_hit;for( uint j = j_min ; j < j_lim && count < 2 ; j++ ){CO uint index = start + j * depth - N_input_shift + N_input_start;if( f[index] != zero ){if( count == 0 ){index_hit = index;j_hit = j;}count++;}}if( count == 1 ){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };T zeta_power_2{ zeta };WH( j_hit != 0 ){if( j_hit % 2 == 1 ){zeta_power *= zeta_power_2;}zeta_power_2 *= zeta_power_2;j_hit /= 2;}answer[0] = f[index_hit];for( uint i = 1 ; i < two_power ; i++ ){answer[i] = zeta_power * answer[i-1];}} else if( count > 1 ){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };CE CO uint& border = BorderForFFT;if( exponent < border ){for( uint i = 0 ; i < two_power ; i++ ){T& answer_i = answer[i];T zeta_power_power{ one };T zeta_power_power_2{ zeta_power };uint j_min_copy = j_min;WH( j_min_copy != 0 ){if( j_min_copy % 2 == 1 ){zeta_power_power *= zeta_power_power_2;}zeta_power_power_2 *= zeta_power_power_2;j_min_copy /= 2;}uint index = start + j_min * depth - N_input_shift + N_input_start;for( uint j = j_min ; j < j_lim ; j++ ){answer_i += zeta_power_power * f[index];zeta_power_power *= zeta_power;index += depth;}zeta_power *= zeta;}} else {CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;CO uint depth_sub = depth * 2;VE answer_sub0{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , start , depth_sub , PRT ) ) };VE answer_sub1{ move( FFT_Body( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , start + depth , depth_sub , PRT ) ) };for( uint i = 0 ; i < two_power ; i++ ){CO uint i_sub = i % two_power_sub;answer[i] = answer_sub0[i_sub] + zeta_power * answer_sub1[i_sub];zeta_power *= zeta;}}}}RE answer;}TE IN TP::TP( CO uint& N ) : PO() , m_N( N ) {}TE IN TP::TP( CO TP& f ) : PO( f ) , m_N( f.m_N ) {}TE IN TP::TP( CO uint& N , CO T& t ) : PO( t ) , m_N( N ) {}TE TP::TP( CO uint& N , CO PO& f ) : PO() , m_N( N ){CO uint& size = f.PO::m_size < m_N ? f.PO::m_size : m_N;for( uint i = 0 ; i < size ; i++ ){PO::m_f.push_back( f.PO::m_f[i] );PO::m_size++;}}TE IN TP::TP( CO uint& N , PO&& f ) : PO( move( f ) ) , m_N( N ) {};TE IN TP::TP( CO uint& N , CO uint& i , CO T& t ) : PO() , m_N( N ) { if( i < m_N ? t != PO::CO_zero() : false ){ PO::OP[]( i ) = t; } }TE IN TP::TP( CO uint& N , VE&& f ) : PO( move( f ) ) , m_N( N ){WH( PO::m_size > m_N ){PO::m_f.pop_back();PO::m_size--;}}TE IN TP& TP::OP=( CO TP& f ) { PO::OP=( f ); m_N = f.m_N; RE *this; }TE IN TP& TP::OP=( CO T& t ) { PO::OP=( t ); RE *this; }TE IN TP& TP::OP=( CO PO& f ) { RE OP=( TP( m_N , f ) ); }TE IN TP& TP::OP+=( CO T& t ) { PO::OP+=( t ); RE *this; }TE IN TP& TP::OP+=( CO PO& f ) { RE TP::TruncatedPlus( f , 0 , f.PO::m_size ); }TE IN TP& TP::OP+=( CO TP& f ) { RE m_N == 0 ? OP=( f ) : TP::TruncatedPlus( f , 0 , f.PO::m_size ); }TE TP& TP::TruncatedPlus( CO PO& f , CO uint& N_output_start , CO uint& N_output_limit ){CO uint& size = N_output_limit < m_N ? N_output_limit < f.PO::m_size ? N_output_limit : f.PO::m_size : m_N < f.PO::m_size ? m_N : f.PO::m_size;CO uint& size_min = PO::m_size < size ? PO::m_size : size;for( uint i = N_output_start ; i < size_min ; i++ ){PO::m_f[i] += f.PO::m_f[i];}for( uint i = PO::m_size ; i < size ; i++ ){PO::m_f.push_back( f.PO::m_f[i] );PO::m_size++;}RE *this;}TE IN TP& TP::OP-=( CO T& t ) { PO::OP-=( t ); RE *this; }TE IN TP& TP::OP-=( CO PO& f ) { RE TP::TruncatedMinus( f , 0 , f.PO::m_size ); }TE IN TP& TP::OP-=( CO TP& f ) { RE m_N == 0 ? OP=( -f ) : TP::TruncatedMinus( f , 0 , f.PO::m_size ); }TE TP& TP::TruncatedMinus( CO PO& f , CO uint& N_output_start , CO uint& N_output_limit ){CO uint& size = N_output_limit < m_N ? N_output_limit < f.PO::m_size ? N_output_limit : f.PO::m_size : m_N < f.PO::m_size ? m_N : f.PO::m_size;CO uint& size_min = PO::m_size < size ? PO::m_size : size;for( uint i = N_output_start ; i < size_min ; i++ ){PO::m_f[i] -= f.PO::m_f[i];}for( uint i = PO::m_size ; i < size ; i++ ){PO::m_f.push_back( - f.PO::m_f[i] );PO::m_size++;}RE *this;}TE IN TP& TP::OP*=( CO T& t ) { PO::OP*=( t ); RE *this; }TE TP& TP::OP*=( CO PO& f ){CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO::m_size == 0 );DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( searching );DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= m_N );DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;}RE *this;}TE TP& TP::FFT_MU( CO PO& f ){CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO::m_size == 0 );DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( searching );DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL;PO::m_f = move( IFFT( f0 , 0 , two_power , 0 , 0 , N_output_lim_fixed - N_input_start_0_start_1 , N_input_start_0_start_1 , two_power , two_power_inv , exponent ) );PO::m_size = PO::m_f.size();}}RE *this;}TE TP& TP::TruncatedMU( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;}RE *this;}TE TP& TP::FFT_TruncatedMU( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if( N_output_start < N_input_start_0_start_1 ){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;f0 = move( IFFT( f0 , 0 , two_power , 0 , N_output_start_shifted , N_output_lim_shifted , N_output_shift_shifted , two_power , two_power_inv , exponent ) );SET_VE_FOR_ANSWER_OF_MU_FOR_TRUNCATED_POLYNOMIAL( N_output_lim_fixed );for( uint i = N_output_start ; i < N_output_lim_fixed ; i++ ){PO::m_f[i] = f0[i];}}}RE *this;}TE TP TP::TruncatedMU_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint border_0 = 21;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){DEFINITION_0_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP( m_N , move( answer ) );}TE TP TP::FFT_TruncatedMU_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint& border_0 = FFT_MU_border_0;CO T& zero = PO::CO_zero();bool searching = true;if( PO::m_size < border_0 && f.PO::m_size < border_0 ){DEFINITION_0_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP( m_N , move( answer ) );}DEFINITION_4_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if( N_output_start < N_input_start_0_start_1 ){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;RE TP( m_N , move( IFFT( f0 , 0 , two_power , 0 , N_output_start_shifted , N_output_lim_shifted , N_output_shift_shifted , two_power , two_power_inv , exponent ) ) );}TE IN TP& TP::OP/=( CO T& t ) { PO::OP/=( t ); RE *this; }TE IN TP& TP::OP/=( CO TP& f ) { RE OP*=( Inverse( m_N > f.m_N ? f : TP( m_N , f ) ) ); }TE IN TP& TP::OP%=( CO T& t ) { PO::OP%=( t ); RE *this; }TE IN TP TP::OP-() CO { RE TP( m_N ).OP-=( *this ); }TE IN void TP::SetTruncation( CO uint& N ) NE { m_N = N; TruncateFinal( m_N ); }TE IN CO uint& TP::GetTruncation() CO NE { RE m_N; }TE IN TP& TP::TruncateInitial( CO uint& N ) NE { CO uint& size = N < PO::m_size ? N : PO::m_size; for( uint i = 0 ; i < size ; i++ ){ PO::m_f[i] = 0; } RE *this; }TE IN TP& TP::TruncateFinal( CO uint& N ) NE { WH( PO::m_size > N ){ PO::m_f.pop_back(); PO::m_size--; } RE *this; }TE IN TP OP+( CO TP& f0 , CO P& f1 ) { RE TP( f0 ).OP+=( f1 ); }TE IN TP OP-( CO TP& f ) { RE TP( f ).OP*=( PO::CO_minus_one()); }TE IN TP OP-( CO TP& f0 , CO P& f1 ) { RE TP( f0 ).OP-=( f1 ); }TE IN TP OP*( CO TP& f0 , CO P& f1 ) { RE TP( f0 ).OP*=( f1 ); }TE IN TP OP/( CO TP& f0 , CO P& f1 ) { RE TP( f0 ).OP*=( Inverse( f1 ) ); }TE IN TP OP%( CO TP& f0 , CO T& t1 ) { RE TP( f0 ).OP%=( t1 ); }TE IN TP Differential( CO TP& f ) { RE TruncatedDifferential( f , 1 ); }TE IN TP Differential( CO uint& i , CO TP& f ) { RE i == 0 ? f : Differential( i - 1 , Differential( f ) ); }TE TP TruncatedDifferential( CO TP& f , CO uint& N_output_start_plus_one ){if( f.m_N == 0 ){RE TP();}TP f_dif{ f.m_N - 1 };if( N_output_start_plus_one < f.PO::m_size ){for( uint i = 1 ; i < N_output_start_plus_one ; i++ ){f_dif.PO::m_f.push_back( 0 );}for( uint i = N_output_start_plus_one ; i < f.PO::m_size ; i++ ){f_dif.PO::m_f.push_back( i * f.PO::m_f[i] );}f_dif.PO::m_size = f.PO::m_size - 1;}RE f_dif;}TE IN TP Integral( CO TP& f ) { RE TruncatedIntegral( f , 1 ); }TE TP TruncatedIntegral( CO TP& f , CO uint& N_output_start ){TP f_int{ f.m_N + 1 };if( N_output_start <= f.PO::m_size ){for( uint i = 0 ; i < N_output_start ; i++ ){f_int.PO::m_f.push_back( 0 );}for( uint i = N_output_start ; i <= f.PO::m_size ; i++ ){f_int.PO::m_f.push_back( f.PO::m_f[i - 1] / T( i ) );}f_int.PO::m_size = f.PO::m_size + 1;}RE f_int;}TE TP Inverse( CO TP& f ){DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TruncatedMinus( f_inv.TruncatedMU_CO( f , power , power_2 ).TruncatedMU( f_inv , power , power_2 ) , power , power_2 ) );}TE TP Exp( CO TP& f ){DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).TruncatedMU_CO( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).TruncatedMU( f_exp , power ) , power , power_2 ) );}TE IN TP Log( CO TP& f ) { RE Integral( Differential( f ) /= f ); }TE IN TP Power( CO TP& f , CO T& t ) { RE Exp( Log( f ) *= t ); }DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TRUNCATED_POLYNOMIAL( Mod

, 17 , 512 , 1024 , 10 , 997269505 ); TE IN TP& Prod_Body( LI >& f ){if( f.empty() ){ERR_IMPUT( f );}if( f.size() == 1 ){RE f.front();}auto itr = f.begin() , end = f.end();WH( itr != end ){TP& t = *itr;itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod_Body( f );}TE IN TP& Prod( LI >& f , CO uint& N ){if( f.empty() ){f.push_back( TP( N , PO::CO_one() ) );RE f.front();}if( f.size() == 1 ){TP& t = f.front();t.SetTruncation( N );RE t;}auto itr = f.begin() , end = f.end();WH( itr != end ){TP& t = *itr;t.SetTruncation( N );itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod_Body( f );}TE IN void SetMultipointEvaluation( CO PO& f , CO LI& point , LI& answer );TE void SetMultipointEvaluation_Body( CO PO& f , CO LI > >& point_tree , LI& answer );TE void SetPointTree( CO LI& point , LI > >& point_tree );TE IN void SetMultipointEvaluation( CO PO& f , CO LI& point , LI& answer ) { LI > > pt{}; SetMultipointEvaluation_Body( point , pt ); SetMultipointEvaluation( f , pt , answer ); }TE void SetMultipointEvaluation( CO PO& f , CO LI > >& point_tree , LI& answer ){CO LI >& prod = point_tree.front();if( prod.empty() ){return;}LI > residue = {};CO PO& zero = PO::zero();residue.push_back( zero );residue.back() = move( f % prod.front() );auto itr_tree = point_tree.begin() , end_tree = point_tree.end();itr_tree++;WH( itr_tree != end_tree ){auto itr_residue = residue.begin() , end_residue = residue.end();auto itr_node = itr_tree->begin() , end_node = itr_tree->end();WH( itr_residue != end_residue ){CO TP& f = *itr_node;itr_node++;if( itr_node != end_node ){*( residue.insert( itr_residue , zero ) ) = move( *itr_residue % f );*itr_residue %= *itr_node;itr_node++;}itr_residue++;}itr_tree++;}for( auto itr_residue = residue.begin() , end_residue = residue.end() ; itr_residue != end_residue ; itr_residue++ ){answer.push_back( ( *itr_residue )[0] );}return;}TE void SetPointTree( CO LI& point , LI > >& point_tree ){static CO LI > empty{};point_tree.push_front( empty );LI >& linear = point_tree.front();for( auto itr = point.begin() , end = point.end() ; itr != end ; itr++ ){static CO TP x{ 2 , 1 , PO::CO_one() };linear.push_back( x );linear.back()[0] -= *itr;}LI > *p_node = &( point_tree.back() );WH( p_node->size() > 1 ){point_tree.push_front( empty );LI >& node_curr = point_tree.front();for( auto itr = p_node->begin() , end = p_node->end() ; itr != end ; itr++ ){static CO TP null{};node_curr.push_back( null );TP& f = *itr;itr++;if( itr == end ){node_curr.back() = f;break;} else {TP& g = *itr;CO uint size = f.size() + g.size() - 1;f.SetTruncation( size );g.SetTruncation( size );node_curr.back() = move( f * g );}}p_node = &node_curr;}return;} TE using LineTypeForMA = VE;TE using TableTypeForMA = LineTypeForMA >;using SizeTypeForMA = uint;TE class MA{PR:TableTypeForMA m_M;PU:TE MA( CO Args&... args ) NE;IN MA( CO MA& mat ) NE;IN MA( MA&& mat ) NE;TE IN MA( CO TableTypeForMA& M ) NE;MA& OP=( CO MA& mat ) NE;MA& OP+=( CO MA& mat );MA& OP-=( CO MA& mat );MA& OP*=( CO T& scalar ) NE;IN TableTypeForMA& RefTable() NE;IN CO TableTypeForMA& GetTable() CO NE;static IN CO MA& Unit() NE;PR:static IN void COructTable( TableTypeForMA& M , LineTypeForMA& vec ) NE;TE static void COructTable( TableTypeForMA& M , LineTypeForMA& vec , CO Arg& arg , CO Args&... args ) NE;static MA Unit_Body() NE;};TE IN MA OP==( CO MA& mat1 , CO MA& mat2 ) NE;TE IN MA OP!=( CO MA& mat1 , CO MA& mat2 ) NE;TE MA OP+( CO MA& mat1 , CO MA& mat2 );TE MA OP-( CO MA& mat1 , CO MA& mat2 );TE MA OP*( CO MA& mat1 , CO MA& mat2 );TE MA OP*( CO T& scalar , CO MA& mat );TE MA Transpose( CO MA& mat );TE T Trace( CO MA& mat );TE TE MA::MA( CO Args&... args ) NE: m_M(){TableTypeForMA M{};LineTypeForMA vec{};COructTable( M , vec , args... );m_M = M;}TE IN MA::MA( CO MA& mat ) NE : m_M( mat.m_M ) {}TE IN MA::MA( MA&& mat ) NE : m_M( move( mat.m_M ) ) {}TE TE IN MA::MA( CO TableTypeForMA& M ) NE : m_M( M ) {}TE MA& MA::OP=( CO MA& mat ) NE{m_M = mat.m_M;RE *this;}TE MA& MA::OP+=( CO MA& mat ){auto itr1y = m_M.begin() , end1y = m_M.end();auto itr2y = mat.m_M.begin(); WH( itr1y != end1y ){auto itr1xy = itr1y->begin() , end1xy = itr1y->end();auto itr2xy = itr2y->begin(); WH( itr1xy != end1xy ){*itr1xy += *itr2xy;itr1xy++;itr2xy++;}itr1y++;itr2y++;}RE *this;}TE MA& MA::OP-=( CO MA& mat ){auto itr1y = m_M.begin() , end1y = m_M.end();auto itr2y = mat.m_M.begin(); WH( itr1y != end1y ){auto itr1xy = itr1y->begin() , end1xy = itr1y->end();auto itr2xy = itr2y->begin(); WH( itr1xy != end1xy ){*itr1xy -= *itr2xy;itr1xy++;itr2xy++;}itr1y++;itr2y++;}RE *this;}TE MA& MA::OP*=( CO T& scalar ) NE{for( auto itry = m_M.begin() , endy = m_M.end() ; itry != endy ; itry++ ){for( auto itrxy = itry->begin() , endxy = itry->end() ; itrxy != endxy ; itrxy++ ){*itrxy *= scalar;}}RE *this;}TE IN TableTypeForMA& MA::RefTable() NE { RE m_M; }TE IN CO TableTypeForMA& MA::GetTable() CO NE { RE m_M; }TE IN CO MA& MA::Unit() NE { static CO MA unit = Unit_Body(); RE unit; }TE MA MA::Unit_Body() NE{TableTypeForMA M{};for( SizeTypeForMA y = 0 ; y < Y ; y++ ){LineTypeForMA vec{};for( SizeTypeForMA x = 0 ; x < X ; x++ ){vec.push_back( x == y ? 1 : 0 );}M.push_back( vec );}RE MA( M );}TE IN void MA::COructTable( TableTypeForMA& M , LineTypeForMA& vec ) NE { M.push_back( vec ); vec.clear(); }TE TE void MA::COructTable( TableTypeForMA& M , LineTypeForMA& vec , CO Arg& arg , CO Args&... args ) NE{vec.push_back( arg );if( vec.size() == X ){COructTable( M , vec );}if( M.size() < Y ){COructTable( M , vec , args... );}return;}TE IN MA OP==( CO MA& mat1 , CO MA& mat2 ) NE { RE mat1.GetTable() == mat2.GetTable(); }TE IN MA OP!=( CO MA& mat1 , CO MA& mat2 ) NE { RE !( mat1 == mat2 ); }TE MA OP+( CO MA& mat1 , CO MA& mat2 ){MA mat1_copy = mat1;mat1_copy += mat2;RE mat1_copy;}TE MA OP-( CO MA& mat1 , CO MA& mat2 ){MA mat1_copy = mat1;mat1_copy -= mat2;RE mat1_copy;}TE IN MA OP*( CO MA& mat1 , CO MA& mat2 ){CO TableTypeForMA& M1 = mat1.GetTable();CO TableTypeForMA& M2 = mat2.GetTable();TableTypeForMA M_prod{};auto begin2x = M2.begin();for( auto itr1y = M1.begin() , end1y = M1.end() ; itr1y != end1y ; itr1y++ ){LineTypeForMA vec{};auto begin1yx = itr1y->begin() , end1yx = itr1y->end();for( SizeTypeForMA z = 0 ; z < Z ; z++ ){auto itr1yx = begin1yx;auto itr2x = begin2x;T inner_product{};WH( itr1yx != end1yx ){inner_product += ( *itr1yx ) * ( *itr2x )[z];itr1yx++;itr2x++;}vec.push_back( inner_product );}M_prod.push_back( vec );}RE MA( M_prod );}TE MA OP*( CO T& scalar , CO MA& mat ){MA mat_copy = mat;mat_copy *= scalar;RE mat_copy;}TE MA Transpose( CO MA& mat ){CO TableTypeForMA& M = mat.GetTable();TableTypeForMA M_t{};auto beginy = M.begin();for( auto itr1x = beginy->begin() , end1x = beginy->end() ; itr1x != end1x ; itr1x++ ){M_t.push_back( LineTypeForMA() );}for( auto itry = beginy , endy = M.end() ; itry != endy ; itry++ ){auto itryx = itry->begin() , endyx = itry->end();auto itr_ty = M_t.begin();WH( itryx != endyx ){itr_ty->push_back( *itryx );itryx++;itr_ty++;}}RE MA( M_t );}TE T Trace( CO MA& mat ){int i = 0;T answer =0;CO TableTypeForMA& M = mat.GetTable();for( auto itry = M.begin() , endy = M.end() ; itry != endy ; itry++ ){answer += ( *itry )[i];i++;}RE answer;} int main() { UNTIE; CEXPR( int , bound_T , 100000 ); CIN_ASSERT( T , 1 , bound_T ); CEXPR( ll , bound_N , 1000000000000000000 ); CEXPR( ll , bound_K1 , bound_T ); CEXPR( ll , bound_K2 , bound_N ); using MOD = Mod

; using MODX = PO; using MODTX = TP; MOD zero{ 0 }; MOD one{ 1 }; MOD two{ 2 }; MOD two_inv{ ( P + 1 ) / 2 }; MODX X{ 1 , one }; if( false ){ CEXPR( int , bound_Kr , 407 ); CEXPR( int , bound_Kq , bound_K1 / bound_Kr + 1 ); static LI N[bound_Kq] = {}; static LI K[bound_Kq] = {}; int Kq[bound_T]; FOR( t , 0 , T ){ CIN_ASSERT( Nt , 1 , bound_N ); CIN_ASSERT( Kt , 0 , min( Nt * 2 , bound_K1 ) ); int& Kqt = Kq[t]; if( Kt >= P ){ Kqt = -1; } else { Kqt = Kt / bound_Kr; N[Kqt].push_back( Nt ); K[Kqt].push_back( Kt ); } } static LI answer[bound_Kq] = {}; } else { CEXPR( ll , power_2_15 , 1 << 15 ); REPEAT( T ){ if(VARIABLE_FOR_REPEAT > 10000 ){ cout << "TLE!!!!\n"; } else { CIN_ASSERT( N , 1 , bound_N ); CIN_ASSERT( K , 0 , min( N * 2 , bound_K2 ) ); // if( K >= P ){ // cout << 0 << "\n"; if( K >= 100000 ){ cout << "TLE!!!!\n"; } else { ll Kq = K / power_2_15; MA<2,2,MODX> MNX { X * ( -two ) + two * N , X * ( - X + two * N + one ) * two_inv , one , zero }; LI point{}; FOR( k , Kq * power_2_15 , K ){ point.push_back( k ); } LI > point_tree{}; SetPointTree( point , point_tree ); LI MN[2][2] = {}; FOR( i , 0 , 2 ){ VE& MNXi = MNX.m_M[i]; LI ( &MNi )[2] = MN[i]; FOR( j , 0 , 2 ){ SetMultipointEvaluation( MNXi[j] , point_tree , MNi[j] ); } } MA<2,1,MOD> v{ one , zero }; if( Kq > 0 ){ MOD power_2{ one }; FOR( i , 0 , 15 ){ VE& MNX0 = MNX.m_M[0]; VE& MNX1 = MNX.m_M[1]; MNX = move( MNX * MA<2,2,MODX> { MNX0[0] << power_2 , MNX0[1] << power_2 , MNX1[0] << power_2 , MNX1[1] << power_2 } ); power_2 *= 2; } point.clear(); FOR( k , 0 , Kq ){ point.push_back( k * power_2_15 ); } point_tree.clear(); SetPointTree( point , point_tree ); LI L[2][2] = {}; FOR( i , 0 , 2 ){ VE& MNXi = MNX.m_M[i]; LI ( &Li )[2] = L[i]; FOR( j , 0 , 2 ){ SetMultipointEvaluation( MNXi[j] , point_tree , Li[j] ); } } LI ( &L0 )[2] = L[0]; LI ( &L1 )[2] = L[1]; LI& L00 = L0[0]; LI& L01 = L0[1]; LI& L10 = L1[0]; LI& L11 = L1[1]; WH( ! L00.empty() ){ v = move( MA<2,2,MOD> ( L00.front() , L01.front() , L10.front() , L11.front() ) * v ); L00.pop_front(); L01.pop_front(); L10.pop_front(); L11.pop_front(); } } LI ( &MN0 )[2] = MN[0]; LI ( &MN1 )[2] = MN[1]; LI& MN00 = MN0[0]; LI& MN01 = MN0[1]; LI& MN10 = MN1[0]; LI& MN11 = MN1[1]; WH( ! MN00.empty() ){ v = move( MA<2,2,MOD> ( MN00.front() , MN01.front() , MN10.front() , MN11.front() ) * v ); MN00.pop_front(); MN01.pop_front(); MN10.pop_front(); MN11.pop_front(); } cout << v.m_M[0][0] << "\n"; } } } } QUIT; }