#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 ) constexpr const LL BOUND = VALUE #define CIN( LL , A ) LL A; cin >> A #define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) #define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) #define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) #define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define RETURN( ANSWER ) COUT( ANSWER ); QUIT #define POWER( ANSWER , ARGUMENT , EXPONENT ) TYPE_OF( ARGUMENT ) ANSWER{ 1 }; { TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; } ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; EXPONENT_FOR_SQUARE_FOR_POWER /= 2; } } #define TE template #define TY typename #define IN inline #define OP operator #define CE constexpr #define CO const #define RE return #define NE noexcept #define VE vector #define VA VLArray #define PO Polynomial #define TR Truncated #define RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE OP=( zero ); } #define RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE TRPO( m_N ); } #define SET_VE_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_VE_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CO_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_CO_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_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_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ PO::m_f[i] = 0; } #define ZEROIFICATION_FOR_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ answer[i] = 0; } #ifndef CONNECT #define CONNECT( S1 , S2 ) SUBSTITUTE_CONNECT( S1 , S2 ) #define SUBSTITUTE_CONNECT( S1 , S2 ) S1 ## S2 #endif #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_VE_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_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CO , 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_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CO ) #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_CO_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_VE_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; } CONNECT( CONNECT( ZEROIFICATION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL ); #define DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) #define DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CO ) #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_CO_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 >::CO_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 >::CO_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 <> CE CO uint FFT_Multiplication_border_0< TYPE > = BORDER_0; TE <> CE CO uint FFT_Multiplication_border_1< TYPE > = BORDER_1; TE <> CE CO uint FFT_Multiplication_border_1_2< TYPE > = BORDER_1_2; TE <> CE CO uint FFT_Multiplication_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> CE 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_CO( 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_CO( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TRMinus( f , power , power_2 ) ).FFT_TRMultiplication( f_exp , power , power_2 ) , power , power_2 ) ); } 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( 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 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& 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 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 != 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( 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();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 == 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 T& t ){if( t == CO_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 ){return;}CO T& z = CO_zero();while( 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 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 , CO uint& N_output_start_plus_one );TE TRPO TRIntegral( CO TRPO& f , CO uint& N_output_start );TE class TRPO :public PO{friend TRPO TRDifferential( CO TRPO& f , CO uint& N_output_start_plus_one );friend TRPO TRIntegral( CO TRPO& f , CO uint& N_output_start );private:uint m_N;public:IN TRPO( CO uint& N = 0 );IN TRPO( CO TRPO& f );IN TRPO( CO uint& N , CO T& t );TRPO( CO uint& N , CO PO& f );IN TRPO( CO uint& N , CO uint& i , CO T& t );IN TRPO( CO uint& 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 , CO uint& N_input_start , CO uint& N_input_limit );IN TRPO& OP-=( CO T& t );IN TRPO& OP-=( CO PO& f );TRPO& TRMinus( CO PO& f , CO uint& N_input_start , CO uint& N_input_limit );IN TRPO& OP*=( CO T& t );TRPO& OP*=( CO PO& f );TRPO& FFT_Multiplication( CO PO& f );TRPO& TRMultiplication( CO PO& f , CO uint& N_input_start , CO uint& N_input_lim );TRPO& FFT_TRMultiplication( CO PO& f , CO uint& N_input_start , CO uint& N_input_lim );TRPO TRMultiplication_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;TRPO FFT_TRMultiplication_CO( CO PO& f , CO uint& N_output_start , CO uint& 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( CO uint& N ) NE;IN CO uint& GetTruncation() CO NE;IN TRPO& TruncateInitial( CO uint& N ) NE;IN TRPO& TruncateFinal( CO uint& N ) NE;};TE IN CE CO uint FFT_Multiplication_border_0;TE IN CE CO uint FFT_Multiplication_border_1;TE IN CE CO uint FFT_Multiplication_border_1_2;TE IN CE CO uint FFT_Multiplication_border_1_2_exponent;TE IN CE 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( CO uint& i , CO TRPO& f );TE TRPO TRDifferential( CO TRPO& f , CO uint& N_output_start_plus_one );TE IN TRPO Integral( CO TRPO& f );TE TRPO TRIntegral( CO TRPO& f , CO uint& 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 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 );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;TE IN basic_ostream& OP<<( basic_ostream& os , CO Mod& n );TE using VA = list;void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ){static VA memory_M{};static VA > 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;return;}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;return;}for( INT_TYPE_FOR_MOD 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 INT Residue( CO INT& M , CO INT& 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 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;}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 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"; }TE IN basic_ostream& OP<<( basic_ostream& os , CO Mod& n ) { RE os << n.Represent(); }TE <> IN CE CO uint LimitOfPowerForFFT > = 24;TE <> IN CE CO uint BorderForFFT > = 4; TE <> IN CO Mod<998244353> ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT >]{static CO Mod<998244353> PRT[ LimitOfPowerForFFT > ] ={Mod<998244353>( 1 ) ,Mod<998244353>( 998244352 ) ,Mod<998244353>( 911660635 ) ,Mod<998244353>( 625715529 ) ,Mod<998244353>( 373294451 ) ,Mod<998244353>( 827987769 ) ,Mod<998244353>( 280333251 ) ,Mod<998244353>( 581015842 ) ,Mod<998244353>( 628092333 ) ,Mod<998244353>( 300892551 ) ,Mod<998244353>( 586046298 ) ,Mod<998244353>( 615001099 ) ,Mod<998244353>( 318017948 ) ,Mod<998244353>( 64341522 ) ,Mod<998244353>( 106061068 ) ,Mod<998244353>( 304605202 ) ,Mod<998244353>( 631920086 ) ,Mod<998244353>( 857779016 ) ,Mod<998244353>( 841431251 ) ,Mod<998244353>( 805775211 ) ,Mod<998244353>( 390359979 ) ,Mod<998244353>( 923521 ) ,Mod<998244353>( 961 ) ,Mod<998244353>( 31 )};RE PRT;}TE <> IN CO Mod<998244353> ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT >]{static CO Mod<998244353> PRT[ LimitOfPowerForFFT > ] ={Mod<998244353>( 1 ) ,Mod<998244353>( 998244352 ) ,Mod<998244353>( 86583718 ) ,Mod<998244353>( 488723995 ) ,Mod<998244353>( 369330050 ) ,Mod<998244353>( 543653592 ) ,Mod<998244353>( 382946991 ) ,Mod<998244353>( 844956623 ) ,Mod<998244353>( 91420391 ) ,Mod<998244353>( 433414612 ) ,Mod<998244353>( 288894979 ) ,Mod<998244353>( 260490556 ) ,Mod<998244353>( 857007890 ) ,Mod<998244353>( 736054570 ) ,Mod<998244353>( 474649464 ) ,Mod<998244353>( 948509906 ) ,Mod<998244353>( 114942468 ) ,Mod<998244353>( 962405921 ) ,Mod<998244353>( 667573957 ) ,Mod<998244353>( 46809892 ) ,Mod<998244353>( 304321983 ) ,Mod<998244353>( 30429817 ) ,Mod<998244353>( 293967900 ) ,Mod<998244353>( 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++;}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 , 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 };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 };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;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 IN TRPO::TRPO( CO uint& N ) : PO() , m_N( N ) {}TE IN TRPO::TRPO( CO TRPO& f ) : PO( f ) , m_N( f.m_N ) {}TE IN TRPO::TRPO( CO uint& N , CO T& t ) : PO( t ) , m_N( N ) {}TE TRPO::TRPO( 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 TRPO::TRPO( 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 TRPO::TRPO( CO uint& 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 , 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 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 , 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 TRPO& TRPO::OP*=( CO T& t ) { PO::OP*=( t ); RE *this; }TE TRPO& TRPO::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_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 ){CE CO uint& border_0 = FFT_Multiplication_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_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;CE CO uint& 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 , 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 TRPO& TRPO::TRMultiplication( 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_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 , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint& border_0 = FFT_Multiplication_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_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;CE CO uint& 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_VE_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_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_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_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_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO( m_N , move( answer ) );}TE TRPO TRPO::FFT_TRMultiplication_CO( CO PO& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint& border_0 = FFT_Multiplication_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_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_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_MULTIPLICATION_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_Multiplication_border_1;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO( m_N , move( answer ) );}DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_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 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( CO uint& N ) NE { m_N = N; TruncateFinal( m_N ); }TE IN CO uint& TRPO::GetTruncation() CO NE { RE m_N; }TE IN TRPO& TRPO::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 TRPO& TRPO::TruncateFinal( CO uint& 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::CO_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( CO uint& i , CO TRPO& f ) { RE i == 0 ? f : Differential( i - 1 , Differential( f ) ); }TE TRPO TRDifferential( CO TRPO& f , CO uint& 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 , CO uint& 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_CO( 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_CO( 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<998244353> , 17 , 512 , 1024 , 10 , 997269505 ); int main(){UNTIE;CEXPR( ll , P , 998244353 );CEXPR( int , bound_N , 200000 );CIN_ASSERT( N , 1 , bound_N );CIN_ASSERT( M , 1 , min( 300 , N ) );uint A[bound_N];uint AB[bound_N];CEXPR( uint , bound , 300 );FOR( i , 0 , N ){CIN_ASSERT( Ai , 1 , bound );A[i] = Ai;}FOR( i , 0 , N ){CIN_ASSERT( Bi , 1 , bound );AB[i] = A[i] + Bi;}uint d_A = 0;uint D = 1;FOR( i , 0 , M ){d_A += A[i];D += AB[i];}using MOD = Mod

;CEXPR( uint , bound2 , bound * 2 + 1 );MOD factorial[bound2];MOD factorial_inverse[bound2];MOD factorial_curr{ 1 };MOD factorial_inverse_curr{ 1 };factorial[0] = factorial_inverse[0] = factorial_curr;FOR( i , 1 , bound2 ){factorial[i] = factorial_curr *= i;factorial_inverse[i] = factorial_inverse_curr /= i;}using F = TRPO;list f{};int N_div , j , Mji;uint dMji;MOD coef;FOR( i , 0 , M ){uint& Ai = A[i];uint& ABi = AB[i];MOD& factorial_ABi = factorial[ABi];N_div = ( N - 1 - i ) / M;f.push_back( F( D ) );F& fi = f.back();FOREQ( di , 0 , ABi ){coef = factorial_ABi * factorial_inverse[di] * factorial_inverse[ABi - di];j = 0;Mji = i;while( ++j <= N_div ){Mji += M;dMji = di + A[Mji];if( dMji < Ai ){coef = 0;break;}dMji -= Ai;uint& ABMji = AB[Mji];if( dMji <= ABMji ){coef *= factorial[ABMji] * factorial_inverse[dMji] * factorial_inverse[ABMji - dMji];} else {coef = 0;break;}}if( coef != 0 ){fi[di] = coef;}}}while( f.size() != 1 ){auto itr = f.begin() , end = f.end();while( itr != end ){F& fi = *itr;itr++;if( itr != end ){fi *= *itr;itr = f.erase( itr );}}}RETURN( f.front()[d_A].Represent() );}