#define CONST_INT_REF INT #define CONST_UINT_REF uint #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define TE template #define TY typename #define IN inline #define OP operator #define CO const #define RE return #define NE noexcept #define VE vector #define RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE OP=( zero ); } #define RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE TrPo( m_N ); } #define SET_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_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_VECTOR_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) VE answer( N_OUTPUT_LIM ) #define SET_SUM_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL Po::m_f[i] = sum #define SET_SUM_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL answer[i] = sum #define SET_N_INPUT_START_FOR_MULTIPLICATION_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_MULTIPLICATION_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_MULTIPLICATION_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_MULTIPLICATION_CONST_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 SUBSTITUTE_CONNECT( S1 , S2 ) S1 ## S2 #define CONNECT( S1 , S2 ) SUBSTITUTE_CONNECT( S1 , S2 ) #define DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , ACCESS_ENTRY ) CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _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; CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _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 ); } CONNECT( CONNECT( SET_SUM_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL ); searching = i > 0; } #define DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION , Po::m_f[j] ) #define DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST , Po::OP[]( j ) ) #define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po::m_f , Po::m_size , N_input_start_0 ); CONNECT( CONNECT( RETURN_ZERO_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Po::m_size , N_input_start_1 ); #define DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) #define DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST ) #define DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Po::m_f , Po::m_size , N_input_max_0 ); SET_N_INPUT_MAX_FOR_MULTIPLICATION_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_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL #define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) 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; CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim_fixed ); for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){ CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _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-- ){ CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_input_start_0 ); searching = i > N_input_start_0_start_1; } #define DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) #define DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST ) #define DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL uint two_power = FFT_Multiplication_border_1_2; uint exponent = FFT_Multiplication_border_1_2_exponent; T two_power_inv{ FFT_Multiplication_border_1_2_inv }; while( 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_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL #define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TrPo< TYPE > f_inv{ power_2 , Po< TYPE >::const_one() / f[0] }; while( 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; TrPo< TYPE > f_exp{ power_2 , Po< TYPE >::const_one() }; while( 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_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( TYPE , BORDER_0 , BORDER_1 , BORDER_1_2 , BORDER_1_2_EXPONENT , BORDER_1_2_INV ) TE <> constexpr CO uint FFT_Multiplication_border_0< TYPE > = BORDER_0; TE <> constexpr CO uint FFT_Multiplication_border_1< TYPE > = BORDER_1; TE <> constexpr CO uint FFT_Multiplication_border_1_2< TYPE > = BORDER_1_2; TE <> constexpr CO uint FFT_Multiplication_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> constexpr CO uint FFT_Multiplication_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TrPo< TYPE >& TrPo< TYPE >::OP*=( CO Po< TYPE >& f ) { RE TrPo< TYPE >::FFT_Multiplication( f ); } TE <> TrPo< TYPE > Inverse( CO TrPo< TYPE >& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_inv.TrMinus( f_inv.FFT_TrMultiplication_const( f , power , power_2 ).FFT_TrMultiplication( f_inv , power , power_2 ) , power , power_2 ) ); } TE <> TrPo< TYPE > Exp( CO TrPo< TYPE >& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_exp.TrMinus( ( TrIntegral( Differential( f_exp ).FFT_TrMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TrMinus( f , power , power_2 ) ).FFT_TrMultiplication( f_exp , power , power_2 ) , power , power_2 ) ); } #define MOD Mod

#include using namespace std;using uint = unsigned int;using ll = long long;constexpr CO ll P = 998244353; constexpr CO ll Q = 999630629; TE INT Residue( CONST_INT_REF M , CONST_INT_REF n ) NE; TE INT Residue( CONST_INT_REF M , CONST_INT_REF n ) NE { if( M == 0 ){ RE 0; } CO INT M_abs = ( M > 0 ? M : -M ); if( n < 0 ){ CO INT n_abs = -n; CO INT res = n_abs % M_abs; RE res == 0 ? res : M_abs - res; } RE n % M_abs; } TE using VLArray = list; using INT_TYPE_FOR_MOD = long long int; TE class Mod { protected: INT_TYPE_FOR_MOD m_n; INT_TYPE_FOR_MOD m_inv; public: IN Mod() NE; IN Mod( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod( CO Mod& n ) NE; IN Mod& OP=( CO INT_TYPE_FOR_MOD& n ) NE; Mod& OP=( CO Mod& n ) NE; Mod& OP+=( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod& OP+=( CO Mod& n ) NE; IN Mod& OP-=( CO INT_TYPE_FOR_MOD& n ) NE; IN Mod& OP-=( CO Mod& n ) NE; Mod& OP*=( CO INT_TYPE_FOR_MOD& n ) NE; Mod& OP*=( CO Mod& n ) NE; virtual Mod& OP/=( CO INT_TYPE_FOR_MOD& n ); virtual Mod& OP/=( CO Mod& n ); Mod& OP%=( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& Represent() CO NE; void Invert() NE; bool CheckInvertible() NE; bool IsSmallerThan( CO INT_TYPE_FOR_MOD& n ) CO NE; bool IsBiggerThan( CO INT_TYPE_FOR_MOD& n ) CO NE; }; TE IN bool OP==( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP==( CO INT_TYPE_FOR_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 Mod& n1 ) NE; TE IN bool OP!=( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP!=( CO INT_TYPE_FOR_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 Mod& n1 ) NE; TE IN bool OP<( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP<( CO INT_TYPE_FOR_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 INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP<=( CO INT_TYPE_FOR_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 Mod& n1 ) NE; TE IN bool OP>( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP>( CO INT_TYPE_FOR_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 Mod& n1 ) NE; TE IN bool OP>=( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE IN bool OP>=( CO INT_TYPE_FOR_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 Mod& n1 ) NE; TE Mod OP+( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE Mod OP+( CO INT_TYPE_FOR_MOD& n0 , CO Mod& n1 ) NE; TE Mod OP+( CO Mod& n0 , CO Mod& n1 ) NE; TE IN Mod OP-( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE Mod OP-( CO INT_TYPE_FOR_MOD& n0 , CO Mod& n1 ) NE; TE Mod OP-( CO Mod& n0 , CO Mod& n1 ) NE; TE Mod OP*( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE; TE Mod OP*( CO INT_TYPE_FOR_MOD& n0 , CO Mod& n1 ) NE; TE Mod OP*( CO Mod& n0 , CO Mod& n1 ) NE; TE Mod OP/( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ); TE Mod OP/( CO INT_TYPE_FOR_MOD& n0 , CO Mod& n1 ); TE Mod OP/( CO Mod& n0 , CO Mod& n1 ); TE Mod OP%( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ); TE IN Mod OP%( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& p , CO string& method = "normal" ); TE <> IN Mod<2> Power( CO Mod<2>& n , CO INT_TYPE_FOR_MOD& 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; void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ); TE IN Mod::Mod() NE : m_n( 0 ) , m_inv( M ){} TE IN Mod::Mod( CO INT_TYPE_FOR_MOD& n ) NE : m_n( Residue( M , n ) ) , 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 INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n ) NE { m_n = Residue( M , m_n + n ); 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 INT_TYPE_FOR_MOD& n ) NE { RE OP+=( -n ); } TE IN Mod& Mod::OP-=( CO Mod& n ) NE { RE OP-=( n.m_n ); } TE Mod& Mod::OP*=( CO INT_TYPE_FOR_MOD& n ) NE { m_n = Residue( M , m_n * n ); m_inv = 0; RE *this; } TE Mod& Mod::OP*=( CO Mod& n ) NE { m_n = Residue( M , m_n * n.m_n ); 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 , m_inv * n.m_inv ); } RE *this; } TE Mod& Mod::OP/=( CO INT_TYPE_FOR_MOD& n ) { RE OP/=( Mod( n ) ); } TE Mod& Mod::OP/=( CO Mod& n ) { RE OP*=( Inverse( n ) ); } TE Mod& Mod::OP%=( CO INT_TYPE_FOR_MOD& n ) { m_n %= Residue( M , n ); 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 INT_TYPE_FOR_MOD& Mod::Represent() CO NE { RE m_n; } TE void Mod::Invert() NE { if( CheckInvertible() ){ INT_TYPE_FOR_MOD i = m_inv; m_inv = m_n; m_n = i; } else { m_n = M; m_inv = M; } RE; } 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 INT_TYPE_FOR_MOD& n ) CO NE { RE m_n < Residue( M , n ); } TE IN bool Mod::IsBiggerThan( CO INT_TYPE_FOR_MOD& n ) CO NE { RE m_n > Residue( M , n ); } TE IN bool OP==( CO Mod& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0 == Mod( n1 ); } TE IN bool OP==( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 == n1 ); } TE IN bool OP!=( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE n0.IsSmallerThan( n1 ); } TE IN bool OP<( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE !( n1 < n0 ); } TE IN bool OP<=( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE n1 < n0; } TE IN bool OP>( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 < n1 ); } TE IN bool OP>=( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { auto n = n0; n += n1; RE n; } TE IN Mod OP+( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { RE n0 + ( -n1 ); } TE IN Mod OP-( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) NE { auto n = n0; n *= n1; RE n; } TE IN Mod OP*( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) { RE n0 / Mod( n1 ); } TE IN Mod OP/( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& n1 ) { auto n = n0; n %= n1; RE n; } TE IN Mod OP%( CO INT_TYPE_FOR_MOD& 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 INT_TYPE_FOR_MOD& p , CO string& method ) { if( p >= 0 ){ RE Power,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method ); } RE Inverse( Power( n , -p , method ) ); } TE <> IN Mod<2> Power( CO Mod<2>& n , CO INT_TYPE_FOR_MOD& p , CO string& method ) { RE p == 0 ? 1 : n; } TE IN Mod Power( CO Mod& n , CO Mod& p , CO string& method ) { RE Power,INT_TYPE_FOR_MOD>( 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"; } void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ) { static VLArray memory_M{}; static VLArray > memory_inverse{}; auto itr_M = memory_M.begin() , end_M = memory_M.end(); auto itr_inverse = memory_inverse.begin(); VE* p_inverse = nullptr; while( 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 INT_TYPE_FOR_MOD size = p_inverse->size(); for( INT_TYPE_FOR_MOD i = size ; i <= n ; i++ ){ p_inverse->push_back( 0 ); } INT_TYPE_FOR_MOD& n_inv = ( *p_inverse )[n]; if( n_inv != 0 ){ m = n_inv; RE; } CO INT_TYPE_FOR_MOD M_abs = M >= 0 ? M : -M; CO INT_TYPE_FOR_MOD n_sub = M_abs % n; INT_TYPE_FOR_MOD 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; RE; } for( INT_TYPE_FOR_MOD i = 1 ; i < M_abs ; i++ ){ if( ( n * i ) % M_abs == 1 ){ n_inv = i; m = n_inv; RE; } } n_inv = M; m = n_inv; RE; } TE IN constexpr CO uint LimitOfPowerForFFT; TE IN constexpr CO uint BorderForFFT; TE IN CO T ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT]; TE IN CO T ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT]; TE IN VE FFT( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ); TE IN VE FFT( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent ); TE VE IFFT( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ); TE VE IFFT( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF exponent ); TE <> IN constexpr CO uint LimitOfPowerForFFT = 24; TE <> IN constexpr 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CO T ( &PRT )[LimitOfPowerForFFT] ); TE static VE FFT_Body( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CONST_UINT_REF start , CONST_UINT_REF depth , CO T ( &PRT )[LimitOfPowerForFFT] ); TE IN VE FFT( CO VE& f , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CO T& two_power_inv , CONST_UINT_REF 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim , CONST_UINT_REF N_output_shift , CONST_UINT_REF two_power , CONST_UINT_REF 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++; } while( 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 , CONST_UINT_REF N_input_start , CONST_UINT_REF N_input_lim , CONST_UINT_REF N_input_shift , CONST_UINT_REF two_power , CONST_UINT_REF exponent , CONST_UINT_REF start , CONST_UINT_REF 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 }; while( 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 }; constexpr CONST_UINT_REF 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; while( 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 class TrPo; TE class Po { friend class TrPo; protected: VE m_f; uint m_size; bool m_no_redundant_zero; public: IN Po(); IN Po( CO T& t ); IN Po( CO Po& f ); IN Po( CONST_UINT_REF i , CO T& t ); IN Po( VE&& f ); Po& OP=( CO T& t ); Po& OP=( CO Po& f ); IN CO T& OP[]( CONST_UINT_REF i ) CO; IN T& OP[]( CONST_UINT_REF i ); 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 T& t ); IN Po OP-() CO; 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& const_zero(); static IN CO T& const_one(); static IN CO T& const_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 T& t1 ); TE IN Po OP%( CO Po& f0 , CO T& t1 ); TE IN Po::Po() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {} TE IN Po::Po( CO T& t ) : Po() { if( t != const_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( CONST_UINT_REF i , CO T& t ) : Po() { if( t != const_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[]( CONST_UINT_REF i ) CO { if( m_size <= i ){ RE const_zero(); } RE m_f[i]; } TE IN T& Po::OP[]( CONST_UINT_REF i ) { m_no_redundant_zero = false; if( m_size <= i ){ CO T& z = const_zero(); while( m_size <= i ){ m_f.push_back( z ); m_size++; } } RE m_f[i]; } 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 == const_one() ){ RE *this; } if( t == const_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 == const_one() ){ RE *this; } RE *this; } TE Po& Po::OP%=( CO T& t ) { if( t == const_one() ){ RE OP=( zero() ); } for( uint i = 0 ; i < m_size ; i++ ){ OP[]( i ) %= t; } RE *this; } TE IN Po Po::OP-() CO { Po().OP-=( *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 ){ RE; } CO T& z = const_zero(); while( m_size > 0 ? m_f[m_size - 1] == z : false ){ m_f.pop_back(); m_size--; } m_no_redundant_zero = true; RE; } 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::const_zero() { static CO T z{ 0 }; RE z; } TE IN CO T& Po::const_one() { static CO T o{ 1 }; RE o; } TE IN CO T& Po::const_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::const_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 T& t1 ) { Po f = f0; RE f.OP/=( t1 ); } TE IN Po OP%( CO Po& f0 , CO T& t1 ) { Po f = f0; RE f.OP%=( t1 ); } TE class TrPo; TE TrPo TrDifferential( CO TrPo& f , CONST_UINT_REF N_output_start_plus_one ); TE TrPo TrIntegral( CO TrPo& f , CONST_UINT_REF N_output_start ); TE class TrPo : public Po { friend TrPo TrDifferential( CO TrPo& f , CONST_UINT_REF N_output_start_plus_one ); friend TrPo TrIntegral( CO TrPo& f , CONST_UINT_REF N_output_start ); private: uint m_N; public: IN TrPo( CONST_UINT_REF N = 0 ); IN TrPo( CO TrPo& f ); IN TrPo( CONST_UINT_REF N , CO T& t ); TrPo( CONST_UINT_REF N , CO Po& f ); IN TrPo( CONST_UINT_REF N , CONST_UINT_REF i , CO T& t ); IN TrPo( CONST_UINT_REF N , VE&& f ); IN TrPo& OP=( CO TrPo& f ); IN TrPo& OP=( CO T& t ); IN TrPo& OP=( CO Po& f ); IN TrPo& OP+=( CO T& t ); IN TrPo& OP+=( CO Po& f ); TrPo& TrPlus( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ); IN TrPo& OP-=( CO T& t ); IN TrPo& OP-=( CO Po& f ); TrPo& TrMinus( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_limit ); IN TrPo& OP*=( CO T& t ); TrPo& OP*=( CO Po& f ); TrPo& FFT_Multiplication( CO Po& f ); TrPo& TrMultiplication( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ); TrPo& FFT_TrMultiplication( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ); TrPo TrMultiplication_const( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO; TrPo FFT_TrMultiplication_const( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO; IN TrPo& OP/=( CO T& t ); IN TrPo& OP/=( CO TrPo& t ); IN TrPo& OP%=( CO T& t ); IN TrPo OP-() CO; IN void SetTruncation( CONST_UINT_REF N ) NE; IN CO uint& GetTruncation() CO NE; IN TrPo& TruncateInitial( CONST_UINT_REF N ) NE; IN TrPo& TruncateFinal( CONST_UINT_REF N ) NE; }; TE IN constexpr CO uint FFT_Multiplication_border_0; TE IN constexpr CO uint FFT_Multiplication_border_1; TE IN constexpr CO uint FFT_Multiplication_border_1_2; TE IN constexpr CO uint FFT_Multiplication_border_1_2_exponent; TE IN constexpr CO uint FFT_Multiplication_border_1_2_inv; TE IN TrPo OP+( CO TrPo& f0 , CO P& f1 ); TE IN TrPo OP-( CO TrPo& f ); TE IN TrPo OP-( CO TrPo& f0 , CO P& f1 ); TE IN TrPo OP*( CO TrPo& f0 , CO P& f1 ); TE IN TrPo OP/( CO TrPo& f0 , CO P& f1 ); TE IN TrPo OP%( CO TrPo& f0 , CO T& t1 ); TE IN TrPo Differential( CO TrPo& f ); TE IN TrPo Differential( CONST_UINT_REF i , CO TrPo& f ); TE TrPo TrDifferential( CO TrPo& f , CONST_UINT_REF N_output_start_plus_one ); TE IN TrPo Integral( CO TrPo& f ); TE TrPo TrIntegral( CO TrPo& f , CONST_UINT_REF N_output_start ); TE TrPo Inverse( CO TrPo& f ); TE TrPo Exp( CO TrPo& f ); TE IN TrPo Log( CO TrPo& f ); TE TrPo Power( CO TrPo& f , CO T& t ); TE IN TrPo::TrPo( CONST_UINT_REF N ) : Po() , m_N( N ) {} TE IN TrPo::TrPo( CO TrPo& f ) : Po( f ) , m_N( f.m_N ) {} TE IN TrPo::TrPo( CONST_UINT_REF N , CO T& t ) : Po( t ) , m_N( N ) {} TE TrPo::TrPo( CONST_UINT_REF 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 TrPo::TrPo( CONST_UINT_REF N , CONST_UINT_REF i , CO T& t ) : Po() , m_N( N ) { if( i < m_N ? t != Po::const_zero() : false ){ Po::OP[]( i ) = t; } } TE IN TrPo::TrPo( CONST_UINT_REF N , VE&& f ) : Po( move( f ) ) , m_N( N ) { while( Po::m_size > m_N ){ Po::m_f.pop_back(); Po::m_size--; } } TE IN TrPo& TrPo::OP=( CO TrPo& f ) { Po::OP=( f ); m_N = f.m_N; RE *this; } TE IN TrPo& TrPo::OP=( CO T& t ) { Po::OP=( t ); RE *this; } TE IN TrPo& TrPo::OP=( CO Po& f ) { RE OP=( TrPo( m_N , f ) ); } TE IN TrPo& TrPo::OP+=( CO T& t ) { Po::OP+=( t ); RE *this; } TE IN TrPo& TrPo::OP+=( CO Po& f ) { RE TrPo::TrPlus( f , 0 , f.Po::m_size ); } TE TrPo& TrPo::TrPlus( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF 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 TrPo& TrPo::OP-=( CO T& t ) { Po::OP-=( t ); RE *this; } TE IN TrPo& TrPo::OP-=( CO Po& f ) { RE TrPo::TrMinus( f , 0 , f.Po::m_size ); } TE TrPo& TrPo::TrMinus( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF 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 TrPo& TrPo::OP*=( CO T& t ) { Po::OP*=( t ); RE *this; } TE TrPo& TrPo::OP*=( CO Po& f ) { constexpr CO uint border_0 = 21; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Po::m_size == 0 ); DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( searching ); DEFINITION_2_OF_MULTIPLICATION_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_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= m_N ); DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } RE *this; } TE TrPo& TrPo::FFT_Multiplication( CO Po& f ) { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Po::m_size == 0 ); DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( searching ); DEFINITION_2_OF_MULTIPLICATION_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_MULTIPLICATION_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; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; Po::m_f = move( IFFT( f0 , 0 , two_power , 0 , N_input_start_0_start_1 , N_output_lim_fixed , N_input_start_0_start_1 , two_power , two_power_inv , exponent ) ); Po::m_size = Po::m_f.size(); } } RE *this; } TE TrPo& TrPo::TrMultiplication( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) { constexpr CO uint border_0 = 21; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_MULTIPLICATION_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_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } RE *this; } TE TrPo& TrPo::FFT_TrMultiplication( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ DEFINITION_0_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_1_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_MULTIPLICATION_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_MULTIPLICATION_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; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL; } else { DEFINITION_4_OF_MULTIPLICATION_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_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_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 TrPo TrPo::TrMultiplication_const( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO { constexpr CO uint border_0 = 21; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo( m_N , move( answer ) ); } DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_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_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed ); DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo( m_N , move( answer ) ); } TE TrPo TrPo::FFT_TrMultiplication_const( CO Po& f , CONST_UINT_REF N_output_start , CONST_UINT_REF N_output_lim ) CO { constexpr CONST_UINT_REF border_0 = FFT_Multiplication_border_0; CO T& zero = Po::const_zero(); bool searching = true; if( Po::m_size < border_0 && f.Po::m_size < border_0 ){ DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo( m_N , move( answer ) ); } DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_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_MULTIPLICATION_CONST_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; constexpr CONST_UINT_REF border_1 = FFT_Multiplication_border_1; if( N_input_truncated_deg_0_deg_1 < border_1 ){ DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL; RE TrPo( m_N , move( answer ) ); } DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_CONST_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 TrPo( 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 TrPo& TrPo::OP/=( CO T& t ) { Po::OP/=( t ); RE *this; } TE IN TrPo& TrPo::OP/=( CO TrPo& f ) { RE OP*=( Inverse( m_N == f.m_N ? f : TrPo( m_N , f ) ) ); } TE IN TrPo& TrPo::OP%=( CO T& t ) { Po::OP%=( t ); RE *this; } TE IN TrPo TrPo::OP-() CO { RE TrPo( m_N ).OP-=( *this ); } TE IN void TrPo::SetTruncation( CONST_UINT_REF N ) NE { m_N = N; TruncateFinal( m_N ); } TE IN CO uint& TrPo::GetTruncation() CO NE { RE m_N; } TE IN TrPo& TrPo::TruncateInitial( CONST_UINT_REF N ) NE { CONST_UINT_REF 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 TrPo& TrPo::TruncateFinal( CONST_UINT_REF N ) NE { while( Po::m_size > N ){ Po::m_f.pop_back(); Po::m_size--; } RE *this; } TE IN TrPo OP+( CO TrPo& f0 , CO P& f1 ) { RE TrPo( f0 ).OP+=( f1 ); } TE IN TrPo OP-( CO TrPo& f ) { RE TrPo( f ).OP*=( Po::const_minus_one()); } TE IN TrPo OP-( CO TrPo& f0 , CO P& f1 ) { RE TrPo( f0 ).OP-=( f1 ); } TE IN TrPo OP*( CO TrPo& f0 , CO P& f1 ) { RE TrPo( f0 ).OP*=( f1 ); } TE IN TrPo OP/( CO TrPo& f0 , CO P& f1 ) { RE TrPo( f0 ).OP*=( Inverse( f1 ) ); } TE IN TrPo OP%( CO TrPo& f0 , CO T& t1 ) { RE TrPo( f0 ).OP%=( t1 ); } TE IN TrPo Differential( CO TrPo& f ) { RE TrDifferential( f , 1 ); } TE IN TrPo Differential( CONST_UINT_REF i , CO TrPo& f ) { RE i == 0 ? f : Differential( i - 1 , Differential( f ) ); } TE TrPo TrDifferential( CO TrPo& f , CONST_UINT_REF N_output_start_plus_one ) { if( f.m_N == 0 ){ RE TrPo(); } TrPo 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 TrPo Integral( CO TrPo& f ) { RE TrIntegral( f , 1 ); } TE TrPo TrIntegral( CO TrPo& f , CONST_UINT_REF N_output_start ) { TrPo 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 TrPo Inverse( CO TrPo& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TrMinus( f_inv.TrMultiplication_const( f , power , power_2 ).TrMultiplication( f_inv , power , power_2 ) , power , power_2 ) ); } TE TrPo Exp( CO TrPo& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TrMinus( ( TrIntegral( Differential( f_exp ).TrMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TrMinus( f , power , power_2 ) ).TrMultiplication( f_exp , power ) , power , power_2 ) ); } TE IN TrPo Log( CO TrPo& f ) { RE Integral( Differential( f ) /= f ); } TE IN TrPo Power( CO TrPo& f , CO T& t ) { RE Exp( Log( f ) *= t ); } DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MULTIPLICATION_OF_TRUNCATED_POLYNOMIAL( MOD , 4 , 4 , 8 , 3 , 873463809 ); int main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); ll N; cin >> N; ll A[100000]; ll sum = 0; FOR( i , 0 , N ){ ll& Ai = A[i]; cin >> Ai; sum += Ai; } MOD coef{}; MOD one = MOD( 1 ); ll D_signed = sum - Q + 1; if( D_signed > 0 ){ sort( A , A + N ); uint B[100000]; ll count[100000]; ll Ai_prev = 0; ll num = -1; FOR( i , 0 , N ){ ll& Ai = A[i]; if( Ai_prev == Ai ){ count[num]++; } else if( Ai < D_signed ){ num++; B[num] = uint( Ai ); count[num] = 1; Ai_prev = Ai; } else { i = N; } } uint D = uint( D_signed ); TrPo f{ D }; num++; FOR( i , 0 , num ){ uint& Bi = B[i]; MOD count_i{ count[i] }; uint j_lim = ( D - 1 ) / Bi + 1; uint d = 0; FOR( j , 1 , j_lim ){ d += Bi; if( j % 2 == 0 ){ f[d] -= count_i / j; } else { f[d] += count_i / j; } } } f = move( Exp( f ) ); FOR( i , 0 , D ){ coef += f[i]; } } MOD m{ one }; MOD power{ 2 }; N--; while( N != 0 ){ if( N % 2 == 1 ){ m *= power; } power = power * power; N /= 2; } cout << ( m * sum - coef * Q ).Represent() << "\n"; RE 0; }