#pragma GCC optimize ( "O3" )
#pragma GCC target ( "avx" )
#include <bits/stdc++.h>
using namespace std;using uint = unsigned int;using ll = long long;
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::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<T>( m_N ); \
 \
} \
 \


#define SET_VE_FOR_ANSWER_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \
if( PO<T>::m_size < N_OUTPUT_LIM ){ \
 \
for( uint i = PO<T>::m_size ; i < N_OUTPUT_LIM ; i++ ){ \
 \
PO<T>::m_f.push_back( 0 ); \
 \
} \
 \
PO<T>::m_size = N_OUTPUT_LIM; \
 \
} \



#define SET_VE_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \
VE<T> answer( N_OUTPUT_LIM ) \


#define SET_SUM_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL \
PO<T>::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<T>::m_f[j] * f.PO<T>::m_f[i - j]; \
 \
} \
 \
PO<T>::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<T>::m_f[j] * f.PO<T>::m_f[i - j]; \
 \
} \
 \


#define ZEROIFICATION_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL \
for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ \
 \
PO<T>::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<T>::m_size == 0 ); \
uint N_output_max = PO<T>::m_size + f.PO<T>::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<T>::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<T>::m_f[j] ) \
 \


#define DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL \
DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CO , PO<T>::OP[]( j ) ) \
 \


#define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) \
SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( PO<T>::m_f , PO<T>::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<T>::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<T>::m_f , PO<T>::m_size , N_input_max_0 ); \
SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.PO<T>::m_size < m_N ? f.PO<T>::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<T>; \
uint exponent = FFT_Multiplication_border_1_2_exponent<T>; \
T two_power_inv{ FFT_Multiplication_border_1_2_inv<T> }; \
 \
while( N_input_truncated_deg_0_deg_1 >= two_power ){ \
 \
two_power *= 2; \
two_power_inv /= 2; \
exponent++; \
 \
} \
 \
VE<T> f0{ move( FFT<T>( PO<T>::m_f , N_input_start_0 , N_input_max_0 + 1 , 0 , two_power , exponent ) ) }; \
CO VE<T> f1{ move( FFT<T>( f.PO<T>::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 <TY T> class TRPO;TE <TY T>class PO{friend class TRPO<T>;protected:VE<T> m_f;uint m_size;bool m_no_redundant_zero;public:IN PO();IN PO( CO T& t );IN PO( CO PO<T>& f );IN PO( CO uint& i , CO T& t );IN PO( VE<T>&& f );PO<T>& OP=( CO T& t );PO<T>& OP=( CO PO<T>& f );IN CO T& OP[]( CO uint& i ) CO;IN T& OP[]( CO uint& i );IN PO<T>& OP+=( CO T& t );PO<T>& OP+=( CO PO<T>& f );IN PO<T>& OP-=( CO T& t );PO<T>& OP-=( CO PO<T>& f );PO<T>& OP*=( CO T& t );PO<T>& OP*=( CO PO<T>& f );PO<T>& OP/=( CO T& t );PO<T>& OP%=( CO T& t );IN PO<T> OP-() CO;IN CO VE<T>& GetCoefficient() CO NE;IN CO uint& size() CO NE;void RemoveRedundantZero();IN string Display() CO NE;static IN CO PO<T>& zero();static IN CO T& CO_zero();static IN CO T& CO_one();static IN CO T& CO_minus_one();};TE <TY T>bool OP==( CO PO<T>& f0 , CO T& t1 );TE <TY T>bool OP==( CO PO<T>& f0 , CO PO<T>& f1 );TE <TY T , TY P> IN bool OP!=( CO PO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN PO<T> OP+( CO PO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN PO<T> OP-( CO PO<T>& f );TE <TY T , TY P> IN PO<T> OP-( CO PO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN PO<T> OP*( CO PO<T>& f0 , CO P& f1 );TE <TY T> IN PO<T> OP/( CO PO<T>& f0 , CO T& t1 );TE <TY T> IN PO<T> OP%( CO PO<T>& f0 , CO T& t1 );TE <TY T> IN PO<T>::PO() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {}TE <TY T> IN PO<T>::PO( CO T& t ) : PO() { if( t != CO_zero() ){ OP[]( 0 ) = t; } }TE <TY T> IN PO<T>::PO( CO PO<T>& f ) : m_f( f.m_f ) , m_size( f.m_size ) , m_no_redundant_zero( f.m_no_redundant_zero ) {}TE <TY T> IN PO<T>::PO( CO uint& i , CO T& t ) : PO() { if( t != CO_zero() ){ OP[]( i ) = t; } }TE <TY T> IN PO<T>::PO( VE<T>&& f ) : m_f( move( f ) ) , m_size( m_f.size() ) , m_no_redundant_zero( false ) {}TE <TY T> IN PO<T>& PO<T>::OP=( CO T& t ) { m_f.clear(); m_size = 0; OP[]( 0 ) = t; RE *this; }TE <TY T> IN PO<T>& PO<T>::OP=( CO PO<T>& f ) { m_f = f.m_f; m_size = f.m_size; m_no_redundant_zero = f.m_no_redundant_zero; RE *this; }TE <TY T>CO T& PO<T>::OP[]( CO uint& i ) CO{if( m_size <= i ){RE CO_zero();}RE m_f[i];}TE <TY T> IN T& PO<T>::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 <TY T> IN PO<T>& PO<T>::OP+=( CO T& t ) { OP[]( 0 ) += t; RE *this; }TE <TY T>PO<T>& PO<T>::OP+=( CO PO<T>& f ){for( uint i = 0 ; i < f.m_size ; i++ ){OP[]( i ) += f.m_f[i];}RE *this;}TE <TY T> IN PO<T>& PO<T>::OP-=( CO T& t ) { OP[]( 0 ) -= t; RE *this; }TE <TY T>PO<T>& PO<T>::OP-=( CO PO<T>& f ){for( uint i = 0 ; i < f.m_size ; i++ ){OP[]( i ) -= f.m_f[i];}RE *this;}TE <TY T>PO<T>& PO<T>::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 <TY T>PO<T>& PO<T>::OP*=( CO PO<T>& 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<T> 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 <TY T>PO<T>& PO<T>::OP/=( CO T& t ){if( t == CO_one() ){RE *this;}for( uint i = 0 ; i < m_size ; i++ ){OP[]( i ) /= t;}RE *this;}TE <TY T>PO<T>& PO<T>::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 <TY T> IN PO<T> PO<T>::OP-() CO { PO<T>().OP-=( *this ); }TE <TY T> IN CO VE<T>& PO<T>::GetCoefficient() CO NE { RE m_f; }TE <TY T> IN CO uint& PO<T>::size() CO NE { RE m_size; }TE <TY T>void PO<T>::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 <TY T>string PO<T>::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 <TY T> IN CO PO<T>& PO<T>::zero() { static CO PO<T> z{}; RE z; }TE <TY T> IN CO T& PO<T>::CO_zero() { static CO T z{ 0 }; RE z; }TE <TY T> IN CO T& PO<T>::CO_one() { static CO T o{ 1 }; RE o; }TE <TY T> IN CO T& PO<T>::CO_minus_one() { static CO T m{ -1 }; RE m; }TE <TY T>bool OP==( CO PO<T>& f0 , CO T& t1 ){CO uint& size = f0.size();CO T& zero = PO<T>::CO_zero();for( uint i = 1 ; i < size ; i++ ){if( f0[i] != zero ){RE false;}}RE f0[0] == t1;}TE <TY T>bool OP==( CO PO<T>& f0 , CO PO<T>& 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 <TY T , TY P> IN bool OP!=( CO PO<T>& f0 , CO P& f1 ) { RE !( f0 == f1 ); }TE <TY T , TY P> IN PO<T> OP+( CO PO<T>& f0 , CO P& f1 ) { PO<T> f = f0; f += f1; RE f; }TE <TY T , TY P> IN PO<T> OP-( CO PO<T>& f ) { RE PO<T>::zero() - f; }TE <TY T , TY P> IN PO<T> OP-( CO PO<T>& f0 , CO P& f1 ) { PO<T> f = f0; RE f.OP-=( f1 ); }TE <TY T , TY P> IN PO<T> OP*( CO PO<T>& f0 , CO P& f1 ) { PO<T> f = f0; RE f.OP*=( f1 ); }TE <TY T> IN PO<T> OP/( CO PO<T>& f0 , CO T& t1 ) { PO<T> f = f0; RE f.OP/=( t1 ); }TE <TY T> IN PO<T> OP%( CO PO<T>& f0 , CO T& t1 ) { PO<T> f = f0; RE f.OP%=( t1 ); }TE <TY T> class TRPO;TE <TY T> TRPO<T> TRDifferential( CO TRPO<T>& f , CO uint& N_output_start_plus_one );TE <TY T> TRPO<T> TRIntegral( CO TRPO<T>& f , CO uint& N_output_start );TE <TY T>class TRPO :public PO<T>{friend TRPO<T> TRDifferential<T>( CO TRPO<T>& f , CO uint& N_output_start_plus_one );friend TRPO<T> TRIntegral<T>( CO TRPO<T>& f , CO uint& N_output_start );private:uint m_N;public:IN TRPO( CO uint& N = 0 );IN TRPO( CO TRPO<T>& f );IN TRPO( CO uint& N , CO T& t );TRPO( CO uint& N , CO PO<T>& f );IN TRPO( CO uint& N , CO uint& i , CO T& t );IN TRPO( CO uint& N , VE<T>&& f );IN TRPO<T>& OP=( CO TRPO<T>& f );IN TRPO<T>& OP=( CO T& t );IN TRPO<T>& OP=( CO PO<T>& f );IN TRPO<T>& OP+=( CO T& t );IN TRPO<T>& OP+=( CO PO<T>& f );TRPO<T>& TRPlus( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_limit );IN TRPO<T>& OP-=( CO T& t );IN TRPO<T>& OP-=( CO PO<T>& f );TRPO<T>& TRMinus( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_limit );IN TRPO<T>& OP*=( CO T& t );TRPO<T>& OP*=( CO PO<T>& f );TRPO<T>& FFT_Multiplication( CO PO<T>& f );TRPO<T>& TRMultiplication( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_lim );TRPO<T>& FFT_TRMultiplication( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_lim );TRPO<T> TRMultiplication_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;TRPO<T> FFT_TRMultiplication_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;IN TRPO<T>& OP/=( CO T& t );IN TRPO<T>& OP/=( CO TRPO<T>& t );IN TRPO<T>& OP%=( CO T& t );IN TRPO<T> OP-() CO;IN void SetTruncation( CO uint& N ) NE;IN CO uint& GetTruncation() CO NE;IN TRPO<T>& TruncateInitial( CO uint& N ) NE;IN TRPO<T>& TruncateFinal( CO uint& N ) NE;};TE <TY T> IN CE CO uint FFT_Multiplication_border_0;TE <TY T> IN CE CO uint FFT_Multiplication_border_1;TE <TY T> IN CE CO uint FFT_Multiplication_border_1_2;TE <TY T> IN CE CO uint FFT_Multiplication_border_1_2_exponent;TE <TY T> IN CE CO uint FFT_Multiplication_border_1_2_inv;TE <TY T , TY P> IN TRPO<T> OP+( CO TRPO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TRPO<T> OP-( CO TRPO<T>& f );TE <TY T , TY P> IN TRPO<T> OP-( CO TRPO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TRPO<T> OP*( CO TRPO<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TRPO<T> OP/( CO TRPO<T>& f0 , CO P& f1 );TE <TY T> IN TRPO<T> OP%( CO TRPO<T>& f0 , CO T& t1 );TE <TY T> IN TRPO<T> Differential( CO TRPO<T>& f );TE <TY T> IN TRPO<T> Differential( CO uint& i , CO TRPO<T>& f );TE <TY T> TRPO<T> TRDifferential( CO TRPO<T>& f , CO uint& N_output_start_plus_one );TE <TY T> IN TRPO<T> Integral( CO TRPO<T>& f );TE <TY T>TRPO<T> TRIntegral( CO TRPO<T>& f , CO uint& N_output_start );TE <TY T>TRPO<T> Inverse( CO TRPO<T>& f );TE <TY T>TRPO<T> Exp( CO TRPO<T>& f );TE <TY T> IN TRPO<T> Log( CO TRPO<T>& f );TE <TY T>TRPO<T> Power( CO TRPO<T>& f , CO T& t );TE <TY T> IN CE CO uint LimitOfPowerForFFT;TE <TY T> IN CE CO uint BorderForFFT;TE <TY T> IN CO T ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<T>];TE <TY T> IN CO T ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<T>];TE <TY T> IN VE<T> FFT( CO VE<T>& f , CO uint& N_input_start , CO uint& N_input_lim , CO uint& N_input_shift , CO uint& two_power , CO uint& exponent );TE <TY T> IN VE<T> FFT( CO VE<T>& 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 <TY T> VE<T> IFFT( CO VE<T>& 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 <TY T> VE<T> IFFT( CO VE<T>& 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 <INT_TYPE_FOR_MOD M>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<M>& n ) NE;IN Mod<M>& OP=( CO INT_TYPE_FOR_MOD& n ) NE;Mod<M>& OP=( CO Mod<M>& n ) NE;Mod<M>& OP+=( CO INT_TYPE_FOR_MOD& n ) NE;IN Mod<M>& OP+=( CO Mod<M>& n ) NE;IN Mod<M>& OP-=( CO INT_TYPE_FOR_MOD& n ) NE;IN Mod<M>& OP-=( CO Mod<M>& n ) NE;Mod<M>& OP*=( CO INT_TYPE_FOR_MOD& n ) NE;Mod<M>& OP*=( CO Mod<M>& n ) NE;virtual Mod<M>& OP/=( CO INT_TYPE_FOR_MOD& n );virtual Mod<M>& OP/=( CO Mod<M>& n );Mod<M>& OP%=( CO INT_TYPE_FOR_MOD& n );IN Mod<M>& OP%=( CO Mod<M>& n );IN Mod<M> OP-() CO NE;IN Mod<M>& OP++() NE;IN Mod<M>& OP++( int ) NE;IN Mod<M>& OP--() NE;IN Mod<M>& 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 <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP-( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 );TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 );TE <INT_TYPE_FOR_MOD M> Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 );TE <INT_TYPE_FOR_MOD M> Mod<M> OP%( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 );TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 );TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 );TE <INT_TYPE_FOR_MOD M> Mod<M> Inverse( CO Mod<M>& n );TE <INT_TYPE_FOR_MOD M> Mod<M> Power( CO Mod<M>& 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 <INT_TYPE_FOR_MOD M> IN Mod<M> Power( CO Mod<M>& n , CO Mod<M>& p , CO string& method = "normal" );TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method );TE <TY T> IN T Square( CO T& t );TE <> IN Mod<2> Square<Mod<2> >( CO Mod<2>& t );TE <INT_TYPE_FOR_MOD M> IN string to_string( CO Mod<M>& n ) NE;TE<INT_TYPE_FOR_MOD M , class Traits> IN basic_ostream<char,Traits>& OP<<( basic_ostream<char,Traits>& os , CO Mod<M>& n );TE <TY T>using VA = list<T>;void LazyEvaluationOfModularInverse( CO INT_TYPE_FOR_MOD& M , CO INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m ){static VA<INT_TYPE_FOR_MOD> memory_M{};static VA<VE<INT_TYPE_FOR_MOD> > memory_inverse{};auto itr_M = memory_M.begin() , end_M = memory_M.end();auto itr_inverse = memory_inverse.begin();VE<INT_TYPE_FOR_MOD>* 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<INT_TYPE_FOR_MOD>() );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 <TY INT>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 <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod() NE : m_n( 0 ) , m_inv( M ){}TE <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod( CO INT_TYPE_FOR_MOD& n ) NE : m_n( Residue<INT_TYPE_FOR_MOD>( M , n ) ) , m_inv( 0 ){}TE <INT_TYPE_FOR_MOD M> IN Mod<M>::Mod( CO Mod<M>& n ) NE : m_n( n.m_n ) , m_inv( 0 ){}TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP=( CO INT_TYPE_FOR_MOD& n ) NE { RE OP=( Mod<M>( n ) ); }TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP=( CO Mod<M>& n ) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP+=( CO INT_TYPE_FOR_MOD& n ) NE{m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n + n );m_inv = 0;RE *this;}TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP+=( CO Mod<M>& n ) NE { RE OP+=( n.m_n ); };TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP-=( CO INT_TYPE_FOR_MOD& n ) NE { RE OP+=( -n ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP-=( CO Mod<M>& n ) NE { RE OP-=( n.m_n ); }TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP*=( CO INT_TYPE_FOR_MOD& n ) NE{m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n );m_inv = 0;RE *this;}TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP*=( CO Mod<M>& n ) NE{m_n = Residue<INT_TYPE_FOR_MOD>( 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<INT_TYPE_FOR_MOD>( M , m_inv * n.m_inv );}RE *this;}TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP/=( CO INT_TYPE_FOR_MOD& n ){RE OP/=( Mod<M>( n ) );}TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP/=( CO Mod<M>& n ){RE OP*=( Inverse( n ) );}TE <INT_TYPE_FOR_MOD M>Mod<M>& Mod<M>::OP%=( CO INT_TYPE_FOR_MOD& n ){m_n %= Residue<INT_TYPE_FOR_MOD>( M , n );m_inv = 0;RE *this;}TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP%=( CO Mod<M>& n ) { RE OP%=( n.m_n ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> Mod<M>::OP-() CO NE { RE Mod<M>( 0 ).OP-=( *this ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP++() NE { RE OP+=( 1 ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP++( int ) NE { RE OP++(); }TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP--() NE { RE OP-=( 1 ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M>& Mod<M>::OP--( int ) NE { RE OP-=(); }TE <INT_TYPE_FOR_MOD M> IN CO INT_TYPE_FOR_MOD& Mod<M>::Represent() CO NE { RE m_n; }TE <INT_TYPE_FOR_MOD M>void Mod<M>::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 <INT_TYPE_FOR_MOD M>bool Mod<M>::CheckInvertible() NE{if( m_inv == 0 ){LazyEvaluationOfModularInverse( M , m_n , m_inv );}RE m_inv != M;}TE <INT_TYPE_FOR_MOD M> IN bool Mod<M>::IsSmallerThan( CO INT_TYPE_FOR_MOD& n ) CO NE { RE m_n < Residue<INT_TYPE_FOR_MOD>( M , n ); }TE <INT_TYPE_FOR_MOD M> IN bool Mod<M>::IsBiggerThan( CO INT_TYPE_FOR_MOD& n ) CO NE { RE m_n > Residue<INT_TYPE_FOR_MOD>( M , n ); }TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0 == Mod<M>( n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 ) == n0; }TE <INT_TYPE_FOR_MOD M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() == n1.Represent(); }TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 == n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0.IsSmallerThan( n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1.IsBiggerThan( n0 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() < n1.Represent(); }TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n1 < n0 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n1 < n0; }TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; }TE <INT_TYPE_FOR_MOD M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; }TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE !( n0 < n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); }TE <INT_TYPE_FOR_MOD M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); }TE <INT_TYPE_FOR_MOD M>Mod<M> OP+( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE{auto n = n0;n += n1;RE n;}TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP+( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 + n0; }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 + n1.Represent(); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE { RE n0 + ( -n1 ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 - n1.Represent() ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 - n1.Represent(); }TE <INT_TYPE_FOR_MOD M>Mod<M> OP*( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) NE{auto n = n0;n *= n1;RE n;}TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP*( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) NE { RE n1 * n0; }TE <INT_TYPE_FOR_MOD M>Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE{auto n = n0;n *= n1;RE n;}TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP/( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ) { RE n0 / Mod<M>( n1 ); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP/( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) / n1; }TE <INT_TYPE_FOR_MOD M>Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 ){auto n = n0;n /= n1;RE n;}TE <INT_TYPE_FOR_MOD M>Mod<M> OP%( CO Mod<M>& n0 , CO INT_TYPE_FOR_MOD& n1 ){auto n = n0;n %= n1;RE n;}TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO INT_TYPE_FOR_MOD& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) % n1.Represent(); }TE <INT_TYPE_FOR_MOD M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 ) { RE n0 % n1.Represent(); }TE <INT_TYPE_FOR_MOD M>Mod<M> Inverse( CO Mod<M>& n ){auto n_copy = n;n_copy.Invert();RE n_copy;}TE <INT_TYPE_FOR_MOD M>Mod<M> Power( CO Mod<M>& n , CO INT_TYPE_FOR_MOD& p , CO string& method ){if( p >= 0 ){RE Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method );}RE Inverse( Power<M>( 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 <INT_TYPE_FOR_MOD M> IN Mod<M> Power( CO Mod<M>& n , CO Mod<M>& p , CO string& method ) { RE Power<Mod<M>,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<Mod<2> >( CO Mod<2>& t ) { RE t; }TE <INT_TYPE_FOR_MOD M> IN string to_string( CO Mod<M>& n ) NE { RE to_string( n.Represent() ) + " + MZ"; }TE<INT_TYPE_FOR_MOD M , class Traits> IN basic_ostream<char,Traits>& OP<<( basic_ostream<char,Traits>& os , CO Mod<M>& n ) { RE os << n.Represent(); }TE <> IN CE CO uint LimitOfPowerForFFT<Mod<998244353> > = 24;TE <> IN CE CO uint BorderForFFT<Mod<998244353> > = 4; TE <> IN CO Mod<998244353> ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<Mod<998244353> >]{static CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={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<Mod<998244353> >]{static CO Mod<998244353> PRT[ LimitOfPowerForFFT<Mod<998244353> > ] ={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 <TY T>static VE<T> FFT_Body( CO VE<T>& 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<T>] );TE <TY T>static VE<T> FFT_Body( CO VE<T>& 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<T>] );TE <TY T> IN VE<T> FFT( CO VE<T>& 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<T>( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , 0 , 1 , PrimitiveRootOfTwoForFFT<T>() ); }TE <TY T> IN VE<T> FFT( CO VE<T>& 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<T>( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , PrimitiveRootOfTwoForFFT<T>() ); }TE <TY T>VE<T> IFFT( CO VE<T>& 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<T> answer{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT<T>() ) ) };CO uint size = answer.size();for( uint i = 0 ; i < size ; i++ ){answer[i] *= two_power_inv;}RE answer;}TE <TY T>VE<T> IFFT( CO VE<T>& 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<T> answer{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , N_output_start , N_output_lim , N_output_shift , two_power , exponent , InversePrimitiveRootOfTwoForFFT<T>() ) ) };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 <TY T>static VE<T> FFT_Body( CO VE<T>& 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<T>] ){CO uint length = N_output_lim - N_output_start + N_output_shift;VE<T> 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<T> answer_sub0{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , 0 , 2 , PRT ) ) };VE<T> answer_sub1{ move( FFT_Body<T>( 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 <TY T>static VE<T> FFT_Body( CO VE<T>& 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<T>] ){VE<T> 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<T>;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<T> answer_sub0{ move( FFT_Body<T>( f , N_input_start , N_input_lim , N_input_shift , two_power_sub , exponent_sub , start , depth_sub , PRT ) ) };VE<T> answer_sub1{ move( FFT_Body<T>( 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 <TY T> IN TRPO<T>::TRPO( CO uint& N ) : PO<T>() , m_N( N ) {}TE <TY T> IN TRPO<T>::TRPO( CO TRPO<T>& f ) : PO<T>( f ) , m_N( f.m_N ) {}TE <TY T> IN TRPO<T>::TRPO( CO uint& N , CO T& t ) : PO<T>( t ) , m_N( N ) {}TE <TY T>TRPO<T>::TRPO( CO uint& N , CO PO<T>& f ) : PO<T>() , m_N( N ){CO uint& size = f.PO<T>::m_size < m_N ? f.PO<T>::m_size : m_N;for( uint i = 0 ; i < size ; i++ ){PO<T>::m_f.push_back( f.PO<T>::m_f[i] );PO<T>::m_size++;}}TE <TY T> IN TRPO<T>::TRPO( CO uint& N , CO uint& i , CO T& t ) : PO<T>() , m_N( N ) { if( i < m_N ? t != PO<T>::CO_zero() : false ){ PO<T>::OP[]( i ) = t; } }TE <TY T> IN TRPO<T>::TRPO( CO uint& N , VE<T>&& f ) : PO<T>( move( f ) ) , m_N( N ){while( PO<T>::m_size > m_N ){PO<T>::m_f.pop_back();PO<T>::m_size--;}}TE <TY T> IN TRPO<T>& TRPO<T>::OP=( CO TRPO<T>& f ) { PO<T>::OP=( f ); m_N = f.m_N; RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP=( CO T& t ) { PO<T>::OP=( t ); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP=( CO PO<T>& f ) { RE OP=( TRPO<T>( m_N , f ) ); }TE <TY T> IN TRPO<T>& TRPO<T>::OP+=( CO T& t ) { PO<T>::OP+=( t ); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP+=( CO PO<T>& f ) { RE TRPO<T>::TRPlus( f , 0 , f.PO<T>::m_size ); }TE <TY T>TRPO<T>& TRPO<T>::TRPlus( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_limit ){CO uint& size = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_size ? N_output_limit : f.PO<T>::m_size : m_N < f.PO<T>::m_size ? m_N : f.PO<T>::m_size;CO uint& size_min = PO<T>::m_size < size ? PO<T>::m_size : size;for( uint i = N_output_start ; i < size_min ; i++ ){PO<T>::m_f[i] += f.PO<T>::m_f[i];}for( uint i = PO<T>::m_size ; i < size ; i++ ){PO<T>::m_f.push_back( f.PO<T>::m_f[i] );PO<T>::m_size++;}RE *this;}TE <TY T> IN TRPO<T>& TRPO<T>::OP-=( CO T& t ) { PO<T>::OP-=( t ); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP-=( CO PO<T>& f ) { RE TRPO<T>::TRMinus( f , 0 , f.PO<T>::m_size ); }TE <TY T>TRPO<T>& TRPO<T>::TRMinus( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_limit ){CO uint& size = N_output_limit < m_N ? N_output_limit < f.PO<T>::m_size ? N_output_limit : f.PO<T>::m_size : m_N < f.PO<T>::m_size ? m_N : f.PO<T>::m_size;CO uint& size_min = PO<T>::m_size < size ? PO<T>::m_size : size;for( uint i = N_output_start ; i < size_min ; i++ ){PO<T>::m_f[i] -= f.PO<T>::m_f[i];}for( uint i = PO<T>::m_size ; i < size ; i++ ){PO<T>::m_f.push_back( - f.PO<T>::m_f[i] );PO<T>::m_size++;}RE *this;}TE <TY T> IN TRPO<T>& TRPO<T>::OP*=( CO T& t ) { PO<T>::OP*=( t ); RE *this; }TE <TY T>TRPO<T>& TRPO<T>::OP*=( CO PO<T>& f ){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0 ){RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO<T>::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 <TY T>TRPO<T>& TRPO<T>::FFT_Multiplication( CO PO<T>& f ){CE CO uint& border_0 = FFT_Multiplication_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0 ){RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO<T>::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<T>;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<T>::m_f = move( IFFT<T>( 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<T>::m_size = PO<T>::m_f.size();}}RE *this;}TE <TY T> TRPO<T>& TRPO<T>::TRMultiplication( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::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 <TY T> TRPO<T>& TRPO<T>::FFT_TRMultiplication( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint& border_0 = FFT_Multiplication_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::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<T>;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<T>( 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<T>::m_f[i] = f0[i];}}}RE *this;}TE <TY T> TRPO<T> TRPO<T>::TRMultiplication_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint border_0 = 21;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0 ){DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO<T>( 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<T>( m_N , move( answer ) );}TE <TY T> TRPO<T> TRPO<T>::FFT_TRMultiplication_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint& border_0 = FFT_Multiplication_border_0<T>;CO T& zero = PO<T>::CO_zero();bool searching = true;if( PO<T>::m_size < border_0 && f.PO<T>::m_size < border_0 ){DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO<T>( 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<T>;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CO_FOR_TRUNCATED_POLYNOMIAL;RE TRPO<T>( 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<T>( m_N , move( IFFT<T>( f0 , 0 , two_power , 0 , N_output_start_shifted , N_output_lim_shifted , N_output_shift_shifted , two_power , two_power_inv , exponent ) ) );}TE <TY T> IN TRPO<T>& TRPO<T>::OP/=( CO T& t ) { PO<T>::OP/=( t ); RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::OP/=( CO TRPO<T>& f ) { RE OP*=( Inverse( m_N == f.m_N ? f : TRPO<T>( m_N , f ) ) ); }TE <TY T> IN TRPO<T>& TRPO<T>::OP%=( CO T& t ) { PO<T>::OP%=( t ); RE *this; }TE <TY T> IN TRPO<T> TRPO<T>::OP-() CO { RE TRPO<T>( m_N ).OP-=( *this ); }TE <TY T> IN void TRPO<T>::SetTruncation( CO uint& N ) NE { m_N = N; TruncateFinal( m_N ); }TE <TY T> IN CO uint& TRPO<T>::GetTruncation() CO NE { RE m_N; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateInitial( CO uint& N ) NE { CO uint& size = N < PO<T>::m_size ? N : PO<T>::m_size; for( uint i = 0 ; i < size ; i++ ){ PO<T>::m_f[i] = 0; } RE *this; }TE <TY T> IN TRPO<T>& TRPO<T>::TruncateFinal( CO uint& N ) NE { while( PO<T>::m_size > N ){ PO<T>::m_f.pop_back(); PO<T>::m_size--; } RE *this; }TE <TY T , TY P> IN TRPO<T> OP+( CO TRPO<T>& f0 , CO P& f1 ) { RE TRPO<T>( f0 ).OP+=( f1 ); }TE <TY T , TY P> IN TRPO<T> OP-( CO TRPO<T>& f ) { RE TRPO<T>( f ).OP*=( PO<T>::CO_minus_one()); }TE <TY T , TY P> IN TRPO<T> OP-( CO TRPO<T>& f0 , CO P& f1 ) { RE TRPO<T>( f0 ).OP-=( f1 ); }TE <TY T , TY P> IN TRPO<T> OP*( CO TRPO<T>& f0 , CO P& f1 ) { RE TRPO<T>( f0 ).OP*=( f1 ); }TE <TY T , TY P> IN TRPO<T> OP/( CO TRPO<T>& f0 , CO P& f1 ) { RE TRPO<T>( f0 ).OP*=( Inverse( f1 ) ); }TE <TY T> IN TRPO<T> OP%( CO TRPO<T>& f0 , CO T& t1 ) { RE TRPO<T>( f0 ).OP%=( t1 ); }TE <TY T> IN TRPO<T> Differential( CO TRPO<T>& f ) { RE TRDifferential<T>( f , 1 ); }TE <TY T> IN TRPO<T> Differential( CO uint& i , CO TRPO<T>& f ) { RE i == 0 ? f : Differential<T>( i - 1 , Differential<T>( f ) ); }TE <TY T>TRPO<T> TRDifferential( CO TRPO<T>& f , CO uint& N_output_start_plus_one ){if( f.m_N == 0 ){RE TRPO<T>();}TRPO<T> f_dif{ f.m_N - 1 };if( N_output_start_plus_one < f.PO<T>::m_size ){for( uint i = 1 ; i < N_output_start_plus_one ; i++ ){f_dif.PO<T>::m_f.push_back( 0 );}for( uint i = N_output_start_plus_one ; i < f.PO<T>::m_size ; i++ ){f_dif.PO<T>::m_f.push_back( i * f.PO<T>::m_f[i] );}f_dif.PO<T>::m_size = f.PO<T>::m_size - 1;}RE f_dif;}TE <TY T> IN TRPO<T> Integral( CO TRPO<T>& f ) { RE TRIntegral<T>( f , 1 ); }TE <TY T>TRPO<T> TRIntegral( CO TRPO<T>& f , CO uint& N_output_start ){TRPO<T> f_int{ f.m_N + 1 };if( N_output_start <= f.PO<T>::m_size ){for( uint i = 0 ; i < N_output_start ; i++ ){f_int.PO<T>::m_f.push_back( 0 );}for( uint i = N_output_start ; i <= f.PO<T>::m_size ; i++ ){f_int.PO<T>::m_f.push_back( f.PO<T>::m_f[i - 1] / T( i ) );}f_int.PO<T>::m_size = f.PO<T>::m_size + 1;}RE f_int;}TE <TY T>TRPO<T> Inverse( CO TRPO<T>& 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 <TY T>TRPO<T> Exp( CO TRPO<T>& 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 <TY T> IN TRPO<T> Log( CO TRPO<T>& f ) { RE Integral<T>( Differential<T>( f ) /= f ); }TE <TY T> IN TRPO<T> Power( CO TRPO<T>& 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 , 20000 );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<P>;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<MOD>;F f{ D };f[0] = 1;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 g{ D };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 ){g[di] = coef;}}f *= g;}RETURN( f[d_A].Represent() );}