#827347 (C++17) No.2166 Paint and Fill

提出ソース
結果

問題	No.2166 Paint and Fill
ユーザー	👑 p-adic
提出日時	2022-12-21 00:00:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	64,272 bytes
コンパイル時間	7,547 ms
コンパイル使用メモリ	307,160 KB
実行使用メモリ	49,912 KB
最終ジャッジ日時	2024-11-18 02:19:49
合計ジャッジ時間	216,649 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 8,960 KB
testcase_01	WA	-
testcase_02	TLE	-
testcase_03	AC	2,057 ms 38,080 KB
testcase_04	AC	2,046 ms 38,084 KB
testcase_05	AC	1,833 ms 40,456 KB
testcase_06	AC	2,045 ms 47,520 KB
testcase_07	AC	2,026 ms 45,932 KB
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 設定２のデバッグ（これはサンプルすら通らないが、どこからバグっているかを特定するための提出）
#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 ) CE CO LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT RE 0 
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"; 
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT 
#define TE template
#define TY typename
#define PU public
#define PR PU
#define IN inline
#define OP operator
#define CE constexpr
#define CO const
#define RE return 
#define NE noexcept
#define WH while
#define VE vector
#define LI list
#define RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE OP=( zero ); }
#define RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) if( CONDITION ){ RE TP<T>( m_N ); }
#define SET_VE_FOR_ANSWER_OF_MU_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_MU_CO_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) VE<T> answer( N_OUTPUT_LIM )
#define SET_SUM_OF_MU_FOR_TRUNCATED_POLYNOMIAL PO<T>::m_f[i] = sum
#define SET_SUM_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL answer[i] = sum
#define SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_START_NUM ) uint N_INPUT_START_NUM; for( uint i = 0 ; i < SIZE && searching ; i++ ){ if( F[i] != zero ){ N_INPUT_START_NUM = i; searching = false; } }
#define SET_N_INPUT_MAX_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_MAX_NUM ) uint N_INPUT_MAX_NUM; searching = true; for( uint i = ( SIZE ) - 1 ; searching ; i-- ){ if( F[i] != zero ){ N_INPUT_MAX_NUM = i; searching = false; } }
#define CONVOLUTION_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; T sum{ zero }; for( uint j = J_MIN ; j <= j_max ; j++ ){ sum += PO<T>::m_f[j] * f.PO<T>::m_f[i - j]; } PO<T>::m_f[i] = sum;
#define CONVOLUTION_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) CO uint j_max = i < N_input_max_0_start_1 ? i - N_input_start_1 : N_input_max_0; T& m_fi = answer[i]; for( uint j = J_MIN ; j <= j_max ; j++ ){ m_fi += PO<T>::m_f[j] * f.PO<T>::m_f[i - j]; }
#define ZEROIFICATION_FOR_MU_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_MU_CO_FOR_TRUNCATED_POLYNOMIAL for( uint i = 0 ; i < N_input_start_0_start_1 ; i++ ){ answer[i] = 0; }
#define CN( S1 , S2 ) SUBSTITUTE_CN( S1 , S2 ) 
#define SUBSTITUTE_CN( S1 , S2 ) S1 ## S2 
#define DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MU , ACCESS_ENTRY ) CN( CN( RETURN_ZERO_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( PO<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; CN( CN( SET_VE_FOR_ANSWER_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim ); for( uint i = N_output_max ; searching ; i-- ){ T sum{ zero }; for( uint j = 0 ; j <= i ; j++ ){ sum += ACCESS_ENTRY * f.PO<T>::OP[]( i - j ); } CN( CN( SET_SUM_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL ); searching = i > 0; }
#define DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( MU , PO<T>::m_f[j] )
#define DEFINITION_0_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO , PO<T>::OP[]( j ) )
#define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( PO<T>::m_f , PO<T>::m_size , N_input_start_0 ); CN( CN( RETURN_ZERO_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL_IF )( searching ); searching = true; SET_N_INPUT_START_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( f , f.PO<T>::m_size , N_input_start_1 );
#define DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MU )
#define DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO ) 
#define DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL SET_N_INPUT_MAX_FOR_MU_FOR_TRUNCATED_POLYNOMIAL( PO<T>::m_f , PO<T>::m_size , N_input_max_0 ); SET_N_INPUT_MAX_FOR_MU_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_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL
#define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) CO uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1; CO uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1; CO uint N_output_max_fixed = N_output_lim_fixed - 1; CN( CN( SET_VE_FOR_ANSWER_OF_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim_fixed ); for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){ CN( CN( CONVOLUTION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( i - N_input_max_1 ); } searching = true; for( uint i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1 : N_output_max_fixed ; searching ; i-- ){ CN( CN( CONVOLUTION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL )( N_input_start_0 ); searching = i > N_input_start_0_start_1; } CN( CN( ZEROIFICATION_FOR_ , MU ) , _FOR_TRUNCATED_POLYNOMIAL );
#define DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MU ) 
#define DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MU_CO ) 
#define DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL uint two_power = FFT_MU_border_1_2<T>; uint exponent = FFT_MU_border_1_2_exponent<T>; T two_power_inv{ FFT_MU_border_1_2_inv<T> }; WH( 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_MU_CO_FOR_TRUNCATED_POLYNOMIAL DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL 
#define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TP< TYPE > f_inv{ power_2 , PO< TYPE >::CO_one() / f[0] }; WH( power_2 < N ){ power = power_2; power_2 *= 2; f_inv.SetTruncation( power_2 ); RECURSION; } f_inv.SetTruncation( N ); RE f_inv
#define DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) CO uint& N = f.GetTruncation(); uint power; uint power_2 = 1; TP< TYPE > f_exp{ power_2 , PO< TYPE >::CO_one() }; WH( power_2 < N ){ power = power_2; power_2 *= 2; f_exp.SetTruncation( power_2 ); RECURSION; } f_exp.SetTruncation( N ); RE f_exp
#define DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TRUNCATED_POLYNOMIAL( TYPE , BORDER_0 , BORDER_1 , BORDER_1_2 , BORDER_1_2_EXPONENT , BORDER_1_2_INV ) TE <> CE CO uint FFT_MU_border_0< TYPE > = BORDER_0; TE <> CE CO uint FFT_MU_border_1< TYPE > = BORDER_1; TE <> CE CO uint FFT_MU_border_1_2< TYPE > = BORDER_1_2; TE <> CE CO uint FFT_MU_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; TE <> CE CO uint FFT_MU_border_1_2_inv< TYPE > = BORDER_1_2_INV; TE <> IN TP< TYPE >& TP< TYPE >::OP*=( CO PO< TYPE >& f ) { RE TP< TYPE >::FFT_MU( f ); } TE <> TP< TYPE > Inverse( CO TP< TYPE >& f ) { DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_inv.TruncatedMinus( f_inv.FFT_TruncatedMU_CO( f , power , power_2 ).FFT_TruncatedMU( f_inv , power , power_2 ) , power , power_2 ) ); } TE <> TP< TYPE > Exp( CO TP< TYPE >& f ) { DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).FFT_TruncatedMU_CO( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).FFT_TruncatedMU( f_exp , power , power_2 ) , power , power_2 ) ); }
TE <TY T> IN T Residue( CO T& a , CO T& p ){ RE a >= 0 ? a % p : p - ( - a - 1 ) % p - 1; }TE <ll M>class Mod{protected:ll m_n;ll m_inv;PU:IN Mod() NE;IN Mod( CO ll& n ) NE;IN Mod( CO Mod<M>& n ) NE;IN Mod<M>& OP=( CO ll& n ) NE;Mod<M>& OP=( CO Mod<M>& n ) NE;Mod<M>& OP+=( CO ll& n ) NE;IN Mod<M>& OP+=( CO Mod<M>& n ) NE;IN Mod<M>& OP-=( CO ll& n ) NE;IN Mod<M>& OP-=( CO Mod<M>& n ) NE;Mod<M>& OP*=( CO ll& n ) NE;Mod<M>& OP*=( CO Mod<M>& n ) NE;virtual Mod<M>& OP/=( CO ll& n );virtual Mod<M>& OP/=( CO Mod<M>& n );Mod<M>& OP%=( CO ll& 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 ll& Represent() CO NE;void Invert() NE;bool CheckInvertible() NE;bool IsSmallerThan( CO ll& n ) CO NE;bool IsBiggerThan( CO ll& n ) CO NE;};TE <ll M> IN bool OP==( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP==( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP!=( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP!=( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP<( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP<( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP<=( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP<=( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP>( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>=( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> IN bool OP>=( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP+( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> Mod<M> OP+( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> IN Mod<M> OP-( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> Mod<M> OP-( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP*( CO Mod<M>& n0 , CO ll& n1 ) NE;TE <ll M> Mod<M> OP*( CO ll& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE;TE <ll M> Mod<M> OP/( CO Mod<M>& n0 , CO ll& n1 );TE <ll M> Mod<M> OP/( CO ll& n0 , CO Mod<M>& n1 );TE <ll M> Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 );TE <ll M> Mod<M> OP%( CO Mod<M>& n0 , CO ll& n1 );TE <ll M> IN Mod<M> OP%( CO ll& n0 , CO Mod<M>& n1 );TE <ll M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 );TE <ll M> Mod<M> Inverse( CO Mod<M>& n );TE <ll M> Mod<M> Power( CO Mod<M>& n , CO ll& p , CO string& method = "normal" );TE <> IN Mod<2> Power( CO Mod<2>& n , CO ll& p , CO string& method );TE <ll 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 <ll M> IN string to_string( CO Mod<M>& n ) NE;TE<ll M , class Traits> IN basic_ostream<char,Traits>& OP<<( basic_ostream<char,Traits>& os , CO Mod<M>& n );void LazyEvaluationOfModularInverse( CO ll& M , CO ll& n , ll& m ){CE CO ll border = 1000000;if( n > border ){CO ll n_minus = M - n;if( n_minus <= border ){LazyEvaluationOfModularInverse( M , n_minus , m );m = M - m;return;} else {m = 1;ll exponent = M - 2;ll power_n = n;WH( exponent != 0 ){if( exponent % 2 == 1 ){( m *= power_n ) %= M;}( power_n *= power_n ) %= M;exponent /= 2;}return;}}static LI<ll> memory_M{};static LI<VE<ll> > memory_inverse{};auto itr_M = memory_M.begin() , end_M = memory_M.end();auto itr_inverse = memory_inverse.begin();VE<ll>* p_inverse = nullptr;WH( itr_M != end_M && p_inverse == nullptr ){if( *itr_M == M ){p_inverse = &( *itr_inverse );}itr_M++;itr_inverse++;}if( p_inverse == nullptr ){memory_M.push_front( M );memory_inverse.push_front( VE<ll>() );p_inverse = &( memory_inverse.front() );p_inverse->push_back( M );}CO ll size = p_inverse->size();for( ll i = size ; i <= n ; i++ ){p_inverse->push_back( 0 );}ll& n_inv = ( *p_inverse )[n];if( n_inv != 0 ){m = n_inv;return;}CO ll M_abs = M >= 0 ? M : -M;CO ll n_sub = M_abs % n;ll n_sub_inv = ( *p_inverse )[n_sub];if( n_sub_inv == 0 ){LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv );}if( n_sub_inv != M ){n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs );m = n_inv;return;}for( ll i = 1 ; i < M_abs ; i++ ){if( ( n * i ) % M_abs == 1 ){n_inv = i;m = n_inv;return;}}n_inv = M;m = n_inv;return;}TE <ll M> IN Mod<M>::Mod() NE : m_n( 0 ) , m_inv( M ){}TE <ll M> IN Mod<M>::Mod( CO ll& n ) NE : m_n( Residue<ll>( n , M ) ) , m_inv( 0 ){}TE <ll M> IN Mod<M>::Mod( CO Mod<M>& n ) NE : m_n( n.m_n ) , m_inv( 0 ){}TE <ll M> IN Mod<M>& Mod<M>::OP=( CO ll& n ) NE { RE OP=( Mod<M>( n ) ); }TE <ll M>Mod<M>& Mod<M>::OP=( CO Mod<M>& n ) NE{m_n = n.m_n;m_inv = n.m_inv;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP+=( CO ll& n ) NE{m_n = Residue<ll>( m_n + n , M );m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP+=( CO Mod<M>& n ) NE { RE OP+=( n.m_n ); };TE <ll M> IN Mod<M>& Mod<M>::OP-=( CO ll& n ) NE { RE OP+=( -n ); }TE <ll M> IN Mod<M>& Mod<M>::OP-=( CO Mod<M>& n ) NE { RE OP-=( n.m_n ); }TE <ll M>Mod<M>& Mod<M>::OP*=( CO ll& n ) NE{m_n = Residue<ll>( m_n * n , M );m_inv = 0;RE *this;}TE <ll M>Mod<M>& Mod<M>::OP*=( CO Mod<M>& n ) NE{m_n = Residue<ll>( m_n * n.m_n , M );if( m_inv == 0 || n.m_inv == 0 ){m_inv = 0;} else if( m_inv == M || n.m_inv == M ){m_inv = M;} else {Residue<ll>( m_inv * n.m_inv , M );}RE *this;}TE <ll M>Mod<M>& Mod<M>::OP/=( CO ll& n ){RE OP/=( Mod<M>( n ) );}TE <ll M>Mod<M>& Mod<M>::OP/=( CO Mod<M>& n ){RE OP*=( Inverse( n ) );}TE <ll M>Mod<M>& Mod<M>::OP%=( CO ll& n ){m_n %= Residue<ll>( n , M );m_inv = 0;RE *this;}TE <ll M> IN Mod<M>& Mod<M>::OP%=( CO Mod<M>& n ) { RE OP%=( n.m_n ); }TE <ll M> IN Mod<M> Mod<M>::OP-() CO NE { RE Mod<M>( 0 ).OP-=( *this ); }TE <ll M> IN Mod<M>& Mod<M>::OP++() NE { RE OP+=( 1 ); }TE <ll M> IN Mod<M>& Mod<M>::OP++( int ) NE { RE OP++(); }TE <ll M> IN Mod<M>& Mod<M>::OP--() NE { RE OP-=( 1 ); }TE <ll M> IN Mod<M>& Mod<M>::OP--( int ) NE { RE OP-=(); }TE <ll M> IN CO ll& Mod<M>::Represent() CO NE { RE m_n; }TE <ll M>void Mod<M>::Invert() NE{if( CheckInvertible() ){ll i = m_inv;m_inv = m_n;m_n = i;} else {m_n = M;m_inv = M;}return;}TE <ll M>bool Mod<M>::CheckInvertible() NE{if( m_inv == 0 ){LazyEvaluationOfModularInverse( M , m_n , m_inv );}RE m_inv != M;}TE <ll M> IN bool Mod<M>::IsSmallerThan( CO ll& n ) CO NE { RE m_n < Residue<ll>( n , M ); }TE <ll M> IN bool Mod<M>::IsBiggerThan( CO ll& n ) CO NE { RE m_n > Residue<ll>( n , M ); }TE <ll M> IN bool OP==( CO Mod<M>& n0 , CO ll& n1 ) NE { RE n0 == Mod<M>( n1 ); }TE <ll M> IN bool OP==( CO ll& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 ) == n0; }TE <ll M> IN bool OP==( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() == n1.Represent(); }TE <ll M> IN bool OP!=( CO Mod<M>& n0 , CO ll& n1 ) NE { RE !( n0 == n1 ); }TE <ll M> IN bool OP!=( CO ll& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); }TE <ll M> IN bool OP!=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 == n1 ); }TE <ll M> IN bool OP<( CO Mod<M>& n0 , CO ll& n1 ) NE { RE n0.IsSmallerThan( n1 ); }TE <ll M> IN bool OP<( CO ll& n0 , CO Mod<M>& n1 ) NE { RE n1.IsBiggerThan( n0 ); }TE <ll M> IN bool OP<( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0.Represent() < n1.Represent(); }TE <ll M> IN bool OP<=( CO Mod<M>& n0 , CO ll& n1 ) NE { RE !( n1 < n0 ); }TE <ll M> IN bool OP<=( CO ll& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); }TE <ll M> IN bool OP<=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n1 < n0 ); }TE <ll M> IN bool OP>( CO Mod<M>& n0 , CO ll& n1 ) NE { RE n1 < n0; }TE <ll M> IN bool OP>( CO ll& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; }TE <ll M> IN bool OP>( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n1 < n0; }TE <ll M> IN bool OP>=( CO Mod<M>& n0 , CO ll& n1 ) NE { RE !( n0 < n1 ); }TE <ll M> IN bool OP>=( CO ll& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); }TE <ll M> IN bool OP>=( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE !( n0 < n1 ); }TE <ll M>Mod<M> OP+( CO Mod<M>& n0 , CO ll& n1 ) NE{auto n = n0;n += n1;RE n;}TE <ll M> IN Mod<M> OP+( CO ll& n0 , CO Mod<M>& n1 ) NE { RE n1 + n0; }TE <ll M> IN Mod<M> OP+( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 + n1.Represent(); }TE <ll M> IN Mod<M> OP-( CO Mod<M>& n0 , CO ll& n1 ) NE { RE n0 + ( -n1 ); }TE <ll M> IN Mod<M> OP-( CO ll& n0 , CO Mod<M>& n1 ) NE { RE Mod<M>( n0 - n1.Represent() ); }TE <ll M> IN Mod<M> OP-( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE { RE n0 - n1.Represent(); }TE <ll M>Mod<M> OP*( CO Mod<M>& n0 , CO ll& n1 ) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP*( CO ll& n0 , CO Mod<M>& n1 ) NE { RE n1 * n0; }TE <ll M>Mod<M> OP*( CO Mod<M>& n0 , CO Mod<M>& n1 ) NE{auto n = n0;n *= n1;RE n;}TE <ll M> IN Mod<M> OP/( CO Mod<M>& n0 , CO ll& n1 ) { RE n0 / Mod<M>( n1 ); }TE <ll M> IN Mod<M> OP/( CO ll& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) / n1; }TE <ll M>Mod<M> OP/( CO Mod<M>& n0 , CO Mod<M>& n1 ){auto n = n0;n /= n1;RE n;}TE <ll M>Mod<M> OP%( CO Mod<M>& n0 , CO ll& n1 ){auto n = n0;n %= n1;RE n;}TE <ll M> IN Mod<M> OP%( CO ll& n0 , CO Mod<M>& n1 ) { RE Mod<M>( n0 ) % n1.Represent(); }TE <ll M> IN Mod<M> OP%( CO Mod<M>& n0 , CO Mod<M>& n1 ) { RE n0 % n1.Represent(); }TE <ll M>Mod<M> Inverse( CO Mod<M>& n ){auto n_copy = n;n_copy.Invert();RE n_copy;}TE <ll M>Mod<M> Power( CO Mod<M>& n , CO ll& p , CO string& method ){if( p >= 0 ){RE Power<Mod<M>,ll>( n , p , 1 , true , true , method );}RE Inverse( Power<M>( n , -p , method ) );}TE <> IN Mod<2> Power( CO Mod<2>& n , CO ll& p , CO string& method ) { RE p == 0 ? 1 : n; }TE <ll M> IN Mod<M> Power( CO Mod<M>& n , CO Mod<M>& p , CO string& method ) { RE Power<Mod<M>,ll>( n , p.Represent() , method ); }TE <> IN Mod<2> Power( CO Mod<2>& n , CO Mod<2>& p , CO string& method ) { RE p == 0 ? 1 : n; }TE <> IN Mod<2> Square<Mod<2> >( CO Mod<2>& t ) { RE t; }TE <ll M> IN string to_string( CO Mod<M>& n ) NE { RE to_string( n.Represent() ) + " + MZ"; }TE<ll M , class Traits> IN basic_ostream<char,Traits>& OP<<( basic_ostream<char,Traits>& os , CO Mod<M>& n ) { RE os << n.Represent(); }
IN CEXPR( ll , P , 998244353 );TE <TY T> class TP;TE <TY T>class PO{friend class TP<T>;protected:VE<T> m_f;uint m_size;bool m_no_redundant_zero;PU:IN PO();IN PO( CO T& t );IN PO( CO PO<T>& f );IN PO( 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 T OP()( CO T& t ) CO;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 PO<T>& f );PO<T>& OP%=( CO T& t );PO<T>& OP%=( CO PO<T>& f );IN PO<T> OP-() CO;PO<T>& OP<<=( CO T& t );IN CO VE<T>& GetCoefficient() CO NE;IN 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 , 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>& f , CO T& t );TE <TY T> IN LI<PO<T> >& Prod( LI<PO<T> >& f );TE <TY T> class TP;TE <TY T> TP<T> TruncatedDifferential( CO TP<T>& f , CO uint& N_output_start_plus_one );TE <TY T> TP<T> TruncatedIntegral( CO TP<T>& f , CO uint& N_output_start );TE <TY T> class TP;TE <TY T> TP<T> TruncatedDifferential( CO TP<T>& f , CO uint& N_output_start_plus_one );TE <TY T> TP<T> TruncatedIntegral( CO TP<T>& f , CO uint& N_output_start );TE <TY T>class TP :PU PO<T>{friend TP<T> TruncatedDifferential<T>( CO TP<T>& f , CO uint& N_output_start_plus_one );friend TP<T> TruncatedIntegral<T>( CO TP<T>& f , CO uint& N_output_start );PR:uint m_N;PU:IN TP( CO uint& N = 0 );IN TP( CO TP<T>& f );IN TP( CO uint& N , CO T& t );TP( CO uint& N , CO PO<T>& f );IN TP( CO uint& N , PO<T>&& f );IN TP( CO uint& N , CO uint& i , CO T& t );IN TP( CO uint& N , VE<T>&& f );IN TP<T>& OP=( CO TP<T>& f );IN TP<T>& OP=( CO T& t );IN TP<T>& OP=( CO PO<T>& f );IN TP<T>& OP+=( CO T& t );IN TP<T>& OP+=( CO PO<T>& f );IN TP<T>& OP+=( CO TP<T>& f );TP<T>& TruncatedPlus( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_limit );IN TP<T>& OP-=( CO T& t );IN TP<T>& OP-=( CO PO<T>& f );IN TP<T>& OP-=( CO TP<T>& f );TP<T>& TruncatedMinus( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_limit );IN TP<T>& OP*=( CO T& t );TP<T>& OP*=( CO PO<T>& f );TP<T>& FFT_MU( CO PO<T>& f );TP<T>& TruncatedMU( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_lim );TP<T>& FFT_TruncatedMU( CO PO<T>& f , CO uint& N_input_start , CO uint& N_input_lim );TP<T> TruncatedMU_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;TP<T> FFT_TruncatedMU_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO;IN TP<T>& OP/=( CO T& t );IN TP<T>& OP/=( CO TP<T>& t );IN TP<T>& OP%=( CO T& t );IN TP<T> OP-() CO;IN void SetTruncation( CO uint& N ) NE;IN CO uint& GetTruncation() CO NE;IN TP<T>& TruncateInitial( CO uint& N ) NE;IN TP<T>& TruncateFinal( CO uint& N ) NE;};TE <TY T> IN CE CO uint FFT_MU_border_0;TE <TY T> IN CE CO uint FFT_MU_border_1;TE <TY T> IN CE CO uint FFT_MU_border_1_2;TE <TY T> IN CE CO uint FFT_MU_border_1_2_exponent;TE <TY T> IN CE CO uint FFT_MU_border_1_2_inv;TE <TY T , TY P> IN TP<T> OP+( CO TP<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TP<T> OP-( CO TP<T>& f );TE <TY T , TY P> IN TP<T> OP-( CO TP<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TP<T> OP*( CO TP<T>& f0 , CO P& f1 );TE <TY T , TY P> IN TP<T> OP/( CO TP<T>& f0 , CO P& f1 );TE <TY T> IN TP<T> OP%( CO TP<T>& f0 , CO T& t1 );TE <TY T> IN TP<T> Differential( CO TP<T>& f );TE <TY T> IN TP<T> Differential( CO uint& i , CO TP<T>& f );TE <TY T> TP<T> TruncatedDifferential( CO TP<T>& f , CO uint& N_output_start_plus_one );TE <TY T> IN TP<T> Integral( CO TP<T>& f );TE <TY T>TP<T> TruncatedIntegral( CO TP<T>& f , CO uint& N_output_start );TE <TY T>TP<T> Inverse( CO TP<T>& f );TE <TY T>TP<T> Exp( CO TP<T>& f );TE <TY T> IN TP<T> Log( CO TP<T>& f );TE <TY T>TP<T> Power( CO TP<T>& f , CO T& t );TE <TY T> IN TP<T>& Prod( LI<TP<T> >& f , CO uint& N );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( PO<T>&& f ) : m_f( move( f.m_f ) ) , m_size( move( f.m_size ) ) , m_no_redundant_zero( move( 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();WH( m_size <= i ){m_f.push_back( z );m_size++;}}RE m_f[i];}TE <TY T> IN T PO<T>::OP()( CO T& t ) CO { RE ( *this % ( PO<T>( 1 , CO_one() ) - t ) )[0]; }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 PO<T>& f ){if( m_size >= f.m_size ){assert( f.m_size > 0 );uint size0 = m_size - f.m_size + 1;TP<T> f0_copy( size0 );for( uint d0 = 0 ; d0 < size0 ; d0++ ){f0_copy.PO<T>::m_f.push_back( m_f[m_size - 1 - d0] );}f0_copy.PO<T>::m_size = size0;f0_copy.PO<T>::m_no_redundant_zero = false;TP<T> f1_copy( size0 );uint size1 = size0 < f.m_size ? size0 : f.m_size;for( uint d1 = 0 ; d1 < size1 ; d1++ ){f1_copy.PO<T>::m_f.push_back( f.m_f[f.m_size - 1 - d1] );}f1_copy.PO<T>::m_size = size1;f1_copy.PO<T>::m_no_redundant_zero = false;f0_copy /= f1_copy;for( uint d0 = 0 ; d0 < size0 ; d0++ ){m_f[d0] = f0_copy[ size0 - 1 - d0 ];}WH( m_size > size0 ){m_f.pop_back();m_size--;}} else {PO<T>::m_f.clear();PO<T>::m_size = 0;PO<T>::m_no_redundant_zero = true;}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>PO<T>& PO<T>::OP%=( CO PO<T>& f ){if( m_size >= f.m_size ){OP-=( TP( m_size , move( *this / f ) ) * f );RemoveRedundantZero();m_no_redundant_zero = true;}RE *this;}TE <TY T> IN PO<T> PO<T>::OP-() CO { RE PO<T>().OP-=( *this ); }TE <TY T >PO<T>& PO<T>::OP<<=( CO T& t ){if( m_size > 0 ){static T factorial_curr = 1;static VE<T> factorial = { 1 , 1 };static T factorial_inv_curr = 1;static VE<T> factorial_inv = { 1 , 1 };uint size = factorial.size();WH( size < m_size ){factorial.push_back( factorial_curr *= size );factorial_inv.push_back( factorial_inv_curr /= size );size++;}for( uint d = 0 ; d < m_size ; d++ ){m_f[d] *= factorial[d];}TP<T> f{ m_size * 2 };T power_t = CO_one();for( uint d = 0 ; d < m_size ; d++ ){f[m_size - 1 - d] = power_t * factorial_inv[d];power_t *= t;}f *= *this;for( uint d = 0 ; d < m_size ; d++ ){m_f[d] = f.PO<T>::m_f[d + m_size - 1] * factorial_inv[d];}}RE *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();WH( 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 , 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> PO<T> OP<<( CO PO<T>& f , CO T& t ) { RE PO<T>( f ) <<= t; };TE <TY T> IN PO<T>& Prod( LI<PO<T> >& f ){if( f.empty() ){f.push_back( PO<T>::CO_one() );}if( f.size() == 1 ){RE f.front();}auto itr = f.begin() , end = f.end();WH( itr != end ){PO<T>& t = *itr;itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod( f );}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 );TE <> IN CE CO uint LimitOfPowerForFFT<Mod<P> > = 24;TE <> IN CE CO uint BorderForFFT<Mod<P> > = 4; TE <> IN CO Mod<P> ( &PrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<Mod<P> >]{static CO Mod<P> PRT[ LimitOfPowerForFFT<Mod<P> > ] ={Mod<P>( 1 ) ,Mod<P>( 998244352 ) ,Mod<P>( 911660635 ) ,Mod<P>( 625715529 ) ,Mod<P>( 373294451 ) ,Mod<P>( 827987769 ) ,Mod<P>( 280333251 ) ,Mod<P>( 581015842 ) ,Mod<P>( 628092333 ) ,Mod<P>( 300892551 ) ,Mod<P>( 586046298 ) ,Mod<P>( 615001099 ) ,Mod<P>( 318017948 ) ,Mod<P>( 64341522 ) ,Mod<P>( 106061068 ) ,Mod<P>( 304605202 ) ,Mod<P>( 631920086 ) ,Mod<P>( 857779016 ) ,Mod<P>( 841431251 ) ,Mod<P>( 805775211 ) ,Mod<P>( 390359979 ) ,Mod<P>( 923521 ) ,Mod<P>( 961 ) ,Mod<P>( 31 )};RE PRT;}TE <> IN CO Mod<P> ( &InversePrimitiveRootOfTwoForFFT() NE )[LimitOfPowerForFFT<Mod<P> >]{static CO Mod<P> PRT[ LimitOfPowerForFFT<Mod<P> > ] ={Mod<P>( 1 ) ,Mod<P>( 998244352 ) ,Mod<P>( 86583718 ) ,Mod<P>( 488723995 ) ,Mod<P>( 369330050 ) ,Mod<P>( 543653592 ) ,Mod<P>( 382946991 ) ,Mod<P>( 844956623 ) ,Mod<P>( 91420391 ) ,Mod<P>( 433414612 ) ,Mod<P>( 288894979 ) ,Mod<P>( 260490556 ) ,Mod<P>( 857007890 ) ,Mod<P>( 736054570 ) ,Mod<P>( 474649464 ) ,Mod<P>( 948509906 ) ,Mod<P>( 114942468 ) ,Mod<P>( 962405921 ) ,Mod<P>( 667573957 ) ,Mod<P>( 46809892 ) ,Mod<P>( 304321983 ) ,Mod<P>( 30429817 ) ,Mod<P>( 293967900 ) ,Mod<P>( 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++;}WH( N_output_start_copy != 0 ){if( N_output_start_copy % 2 == 1 ){zeta_power *= PRT[exponent - digit];}N_output_start_copy /= 2;digit++;}CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;VE<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 };WH( j_hit != 0 ){if( j_hit % 2 == 1 ){zeta_power *= zeta_power_2;}zeta_power_2 *= zeta_power_2;j_hit /= 2;}answer[0] = f[index_hit];for( uint i = 1 ; i < two_power ; i++ ){answer[i] = zeta_power * answer[i-1];}} else if( count > 1 ){CO T& zeta = PRT[exponent];CO T& one = PRT[0];T zeta_power{ one };CE CO uint& border = BorderForFFT<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;WH( j_min_copy != 0 ){if( j_min_copy % 2 == 1 ){zeta_power_power *= zeta_power_power_2;}zeta_power_power_2 *= zeta_power_power_2;j_min_copy /= 2;}uint index = start + j_min * depth - N_input_shift + N_input_start;for( uint j = j_min ; j < j_lim ; j++ ){answer_i += zeta_power_power * f[index];zeta_power_power *= zeta_power;index += depth;}zeta_power *= zeta;}} else {CO uint two_power_sub = two_power / 2;CO uint exponent_sub = exponent - 1;CO uint depth_sub = depth * 2;VE<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 TP<T>::TP( CO uint& N ) : PO<T>() , m_N( N ) {}TE <TY T> IN TP<T>::TP( CO TP<T>& f ) : PO<T>( f ) , m_N( f.m_N ) {}TE <TY T> IN TP<T>::TP( CO uint& N , CO T& t ) : PO<T>( t ) , m_N( N ) {}TE <TY T>TP<T>::TP( 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 TP<T>::TP( CO uint& N , PO<T>&& f ) : PO<T>( move( f ) ) , m_N( N ) {};TE <TY T> IN TP<T>::TP( 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 TP<T>::TP( CO uint& N , VE<T>&& f ) : PO<T>( move( f ) ) , m_N( N ){WH( PO<T>::m_size > m_N ){PO<T>::m_f.pop_back();PO<T>::m_size--;}}TE <TY T> IN TP<T>& TP<T>::OP=( CO TP<T>& f ) { PO<T>::OP=( f ); m_N = f.m_N; RE *this; }TE <TY T> IN TP<T>& TP<T>::OP=( CO T& t ) { PO<T>::OP=( t ); RE *this; }TE <TY T> IN TP<T>& TP<T>::OP=( CO PO<T>& f ) { RE OP=( TP<T>( m_N , f ) ); }TE <TY T> IN TP<T>& TP<T>::OP+=( CO T& t ) { PO<T>::OP+=( t ); RE *this; }TE <TY T> IN TP<T>& TP<T>::OP+=( CO PO<T>& f ) { RE TP<T>::TruncatedPlus( f , 0 , f.PO<T>::m_size ); }TE <TY T> IN TP<T>& TP<T>::OP+=( CO TP<T>& f ) { RE m_N == 0 ? OP=( f ) : TP<T>::TruncatedPlus( f , 0 , f.PO<T>::m_size ); }TE <TY T>TP<T>& TP<T>::TruncatedPlus( 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 TP<T>& TP<T>::OP-=( CO T& t ) { PO<T>::OP-=( t ); RE *this; }TE <TY T> IN TP<T>& TP<T>::OP-=( CO PO<T>& f ) { RE TP<T>::TruncatedMinus( f , 0 , f.PO<T>::m_size ); }TE <TY T> IN TP<T>& TP<T>::OP-=( CO TP<T>& f ) { RE m_N == 0 ? OP=( -f ) : TP<T>::TruncatedMinus( f , 0 , f.PO<T>::m_size ); }TE <TY T>TP<T>& TP<T>::TruncatedMinus( 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 TP<T>& TP<T>::OP*=( CO T& t ) { PO<T>::OP*=( t ); RE *this; }TE <TY T>TP<T>& TP<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_MU_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO<T>::m_size == 0 );DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( searching );DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= m_N );DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;}RE *this;}TE <TY T>TP<T>& TP<T>::FFT_MU( CO PO<T>& f ){CE CO uint& border_0 = FFT_MU_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_MU_FOR_TRUNCATED_POLYNOMIAL_IF( f.PO<T>::m_size == 0 );DEFINITION_0_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( searching );DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;CO uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL;PO<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> TP<T>& TP<T>::TruncatedMU( 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_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;}RE *this;}TE <TY T> TP<T>& TP<T>::FFT_TruncatedMU( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ){CE CO uint& border_0 = FFT_MU_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_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_1_OF_MU_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_MU_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_MU_FOR_TRUNCATED_POLYNOMIAL;} else {DEFINITION_4_OF_MU_FOR_TRUNCATED_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if( N_output_start < N_input_start_0_start_1 ){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;f0 = move( IFFT<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_MU_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> TP<T> TP<T>::TruncatedMU_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_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP<T>( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP<T>( m_N , move( answer ) );}TE <TY T> TP<T> TP<T>::FFT_TruncatedMU_CO( CO PO<T>& f , CO uint& N_output_start , CO uint& N_output_lim ) CO{CE CO uint& border_0 = FFT_MU_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_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP<T>( m_N , move( answer ) );}DEFINITION_1_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;DEFINITION_2_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;if( N_output_lim_fixed > N_output_lim ){N_output_lim_fixed = N_output_lim;}RETURN_ZERO_FOR_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );CO uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;CE CO uint& border_1 = FFT_MU_border_1<T>;if( N_input_truncated_deg_0_deg_1 < border_1 ){DEFINITION_3_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;RE TP<T>( m_N , move( answer ) );}DEFINITION_4_OF_TRUNCATED_MU_CO_FOR_TRUNCATED_POLYNOMIAL;uint N_output_start_shifted;uint N_output_shift_shifted;if( N_output_start < N_input_start_0_start_1 ){N_output_start_shifted = 0;N_output_shift_shifted = N_input_start_0_start_1;} else {N_output_start_shifted = N_output_start - N_input_start_0_start_1;N_output_shift_shifted = N_output_start;}CO uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;RE TP<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 TP<T>& TP<T>::OP/=( CO T& t ) { PO<T>::OP/=( t ); RE *this; }TE <TY T> IN TP<T>& TP<T>::OP/=( CO TP<T>& f ) { RE OP*=( Inverse( m_N > f.m_N ? f : TP<T>( m_N , f ) ) ); }TE <TY T> IN TP<T>& TP<T>::OP%=( CO T& t ) { PO<T>::OP%=( t ); RE *this; }TE <TY T> IN TP<T> TP<T>::OP-() CO { RE TP<T>( m_N ).OP-=( *this ); }TE <TY T> IN void TP<T>::SetTruncation( CO uint& N ) NE { m_N = N; TruncateFinal( m_N ); }TE <TY T> IN CO uint& TP<T>::GetTruncation() CO NE { RE m_N; }TE <TY T> IN TP<T>& TP<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 TP<T>& TP<T>::TruncateFinal( CO uint& N ) NE { WH( PO<T>::m_size > N ){ PO<T>::m_f.pop_back(); PO<T>::m_size--; } RE *this; }TE <TY T , TY P> IN TP<T> OP+( CO TP<T>& f0 , CO P& f1 ) { RE TP<T>( f0 ).OP+=( f1 ); }TE <TY T , TY P> IN TP<T> OP-( CO TP<T>& f ) { RE TP<T>( f ).OP*=( PO<T>::CO_minus_one()); }TE <TY T , TY P> IN TP<T> OP-( CO TP<T>& f0 , CO P& f1 ) { RE TP<T>( f0 ).OP-=( f1 ); }TE <TY T , TY P> IN TP<T> OP*( CO TP<T>& f0 , CO P& f1 ) { RE TP<T>( f0 ).OP*=( f1 ); }TE <TY T , TY P> IN TP<T> OP/( CO TP<T>& f0 , CO P& f1 ) { RE TP<T>( f0 ).OP*=( Inverse( f1 ) ); }TE <TY T> IN TP<T> OP%( CO TP<T>& f0 , CO T& t1 ) { RE TP<T>( f0 ).OP%=( t1 ); }TE <TY T> IN TP<T> Differential( CO TP<T>& f ) { RE TruncatedDifferential<T>( f , 1 ); }TE <TY T> IN TP<T> Differential( CO uint& i , CO TP<T>& f ) { RE i == 0 ? f : Differential<T>( i - 1 , Differential<T>( f ) ); }TE <TY T>TP<T> TruncatedDifferential( CO TP<T>& f , CO uint& N_output_start_plus_one ){if( f.m_N == 0 ){RE TP<T>();}TP<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 TP<T> Integral( CO TP<T>& f ) { RE TruncatedIntegral<T>( f , 1 ); }TE <TY T>TP<T> TruncatedIntegral( CO TP<T>& f , CO uint& N_output_start ){TP<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>TP<T> Inverse( CO TP<T>& f ){DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TruncatedMinus( f_inv.TruncatedMU_CO( f , power , power_2 ).TruncatedMU( f_inv , power , power_2 ) , power , power_2 ) );}TE <TY T>TP<T> Exp( CO TP<T>& f ){DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).TruncatedMU_CO( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).TruncatedMU( f_exp , power ) , power , power_2 ) );}TE <TY T> IN TP<T> Log( CO TP<T>& f ) { RE Integral<T>( Differential<T>( f ) /= f ); }TE <TY T> IN TP<T> Power( CO TP<T>& f , CO T& t ) { RE Exp( Log( f ) *= t ); }DEFINITION_OF_PARTIAL_SPECIALISATION_OF_MU_OF_TRUNCATED_POLYNOMIAL( Mod<P> , 17 , 512 , 1024 , 10 , 997269505 ); TE <TY T> IN TP<T>& Prod_Body( LI<TP<T> >& f ){if( f.empty() ){ERR_IMPUT( f );}if( f.size() == 1 ){RE f.front();}auto itr = f.begin() , end = f.end();WH( itr != end ){TP<T>& t = *itr;itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod_Body( f );}TE <TY T> IN TP<T>& Prod( LI<TP<T> >& f , CO uint& N ){if( f.empty() ){f.push_back( TP<T>( N , PO<T>::CO_one() ) );RE f.front();}if( f.size() == 1 ){TP<T>& t = f.front();t.SetTruncation( N );RE t;}auto itr = f.begin() , end = f.end();WH( itr != end ){TP<T>& t = *itr;t.SetTruncation( N );itr++;if( itr != end ){t *= *itr;itr = f.erase( itr );}}RE Prod_Body( f );}TE <TY T> IN void SetMultipointEvaluation( CO PO<T>& f , CO LI<T>& point , LI<T>& answer );TE <TY T>void SetMultipointEvaluation_Body( CO PO<T>& f , CO LI<LI<PO<T> > >& point_tree , LI<T>& answer );TE <TY T>void SetPointTree( CO LI<T>& point , LI<LI<PO<T> > >& point_tree );TE <TY T> IN void SetMultipointEvaluation( CO PO<T>& f , CO LI<T>& point , LI<T>& answer ) { LI<LI<TP<T> > > pt{}; SetMultipointEvaluation_Body( point , pt ); SetMultipointEvaluation( f , pt , answer ); }TE <TY T>void SetMultipointEvaluation( CO PO<T>& f , CO LI<LI<TP<T> > >& point_tree , LI<T>& answer ){CO LI<TP<T> >& prod = point_tree.front();if( prod.empty() ){return;}LI<PO<T> > residue = {};CO PO<T>& zero = PO<T>::zero();residue.push_back( zero );residue.back() = move( f % prod.front() );auto itr_tree = point_tree.begin() , end_tree = point_tree.end();itr_tree++;WH( itr_tree != end_tree ){auto itr_residue = residue.begin() , end_residue = residue.end();auto itr_node = itr_tree->begin() , end_node = itr_tree->end();WH( itr_residue != end_residue ){CO TP<T>& f = *itr_node;itr_node++;if( itr_node != end_node ){*( residue.insert( itr_residue , zero ) ) = move( *itr_residue % f );*itr_residue %= *itr_node;itr_node++;}itr_residue++;}itr_tree++;}for( auto itr_residue = residue.begin() , end_residue = residue.end() ; itr_residue != end_residue ; itr_residue++ ){answer.push_back( ( *itr_residue )[0] );}return;}TE <TY T>void SetPointTree( CO LI<T>& point , LI<LI<TP<T> > >& point_tree ){static CO LI<TP<T> > empty{};point_tree.push_front( empty );LI<TP<T> >& linear = point_tree.front();for( auto itr = point.begin() , end = point.end() ; itr != end ; itr++ ){static CO TP<T> x{ 2 , 1 , PO<T>::CO_one() };linear.push_back( x );linear.back()[0] -= *itr;}LI<TP<T> > *p_node = &( point_tree.back() );WH( p_node->size() > 1 ){point_tree.push_front( empty );LI<TP<T> >& node_curr = point_tree.front();for( auto itr = p_node->begin() , end = p_node->end() ; itr != end ; itr++ ){static CO TP<T> null{};node_curr.push_back( null );TP<T>& f = *itr;itr++;if( itr == end ){node_curr.back() = f;break;} else {TP<T>& g = *itr;CO uint size = f.size() + g.size() - 1;f.SetTruncation( size );g.SetTruncation( size );node_curr.back() = move( f * g );}}p_node = &node_curr;}return;}
TE <TY T>using LineTypeForMA = VE<T>;TE <TY T>using TableTypeForMA = LineTypeForMA<LineTypeForMA<T> >;using SizeTypeForMA = uint;TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>class MA{PR:TableTypeForMA<T> m_M;PU:TE <TY... Args> MA( CO Args&... args ) NE;IN MA( CO MA<Y,X,T>& mat ) NE;IN MA( MA<Y,X,T>&& mat ) NE;TE <TY... Args> IN MA( CO TableTypeForMA<T>& M ) NE;MA<Y,X,T>& OP=( CO MA<Y,X,T>& mat ) NE;MA<Y,X,T>& OP+=( CO MA<Y,X,T>& mat );MA<Y,X,T>& OP-=( CO MA<Y,X,T>& mat );MA<Y,X,T>& OP*=( CO T& scalar ) NE;IN TableTypeForMA<T>& RefTable() NE;IN CO TableTypeForMA<T>& GetTable() CO NE;static IN CO MA<Y,X,T>& Unit() NE;PR:static IN void COructTable( TableTypeForMA<T>& M , LineTypeForMA<T>& vec ) NE;TE <TY Arg , TY... Args> static void COructTable( TableTypeForMA<T>& M , LineTypeForMA<T>& vec , CO Arg& arg , CO Args&... args ) NE;static MA<Y,X,T> Unit_Body() NE;};TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T> OP==( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ) NE;TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T> OP!=( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ) NE;TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP+( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 );TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP-( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 );TE <SizeTypeForMA Y , SizeTypeForMA X , SizeTypeForMA Z , TY T>MA<Y,Z,T> OP*( CO MA<Y,X,T>& mat1 , CO MA<X,Z,T>& mat2 );TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP*( CO T& scalar , CO MA<Y,X,T>& mat );TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<X,Y,T> Transpose( CO MA<Y,X,T>& mat );TE <SizeTypeForMA X , TY T>T Trace( CO MA<X,X,T>& mat );TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> TE <TY... Args>MA<Y,X,T>::MA( CO Args&... args ) NE: m_M(){TableTypeForMA<T> M{};LineTypeForMA<T> vec{};COructTable( M , vec , args... );m_M = M;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T>::MA( CO MA<Y,X,T>& mat ) NE : m_M( mat.m_M ) {}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T>::MA( MA<Y,X,T>&& mat ) NE : m_M( move( mat.m_M ) ) {}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> TE <TY... Args> IN MA<Y,X,T>::MA( CO TableTypeForMA<T>& M ) NE : m_M( M ) {}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T>& MA<Y,X,T>::OP=( CO MA<Y,X,T>& mat ) NE{m_M = mat.m_M;RE *this;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T>& MA<Y,X,T>::OP+=( CO MA<Y,X,T>& mat ){auto itr1y = m_M.begin() , end1y = m_M.end();auto itr2y = mat.m_M.begin(); WH( itr1y != end1y ){auto itr1xy = itr1y->begin() , end1xy = itr1y->end();auto itr2xy = itr2y->begin(); WH( itr1xy != end1xy ){*itr1xy += *itr2xy;itr1xy++;itr2xy++;}itr1y++;itr2y++;}RE *this;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T>& MA<Y,X,T>::OP-=( CO MA<Y,X,T>& mat ){auto itr1y = m_M.begin() , end1y = m_M.end();auto itr2y = mat.m_M.begin(); WH( itr1y != end1y ){auto itr1xy = itr1y->begin() , end1xy = itr1y->end();auto itr2xy = itr2y->begin(); WH( itr1xy != end1xy ){*itr1xy -= *itr2xy;itr1xy++;itr2xy++;}itr1y++;itr2y++;}RE *this;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> MA<Y,X,T>& MA<Y,X,T>::OP*=( CO T& scalar ) NE{for( auto itry = m_M.begin() , endy = m_M.end() ; itry != endy ; itry++ ){for( auto itrxy = itry->begin() , endxy = itry->end() ; itrxy != endxy ; itrxy++ ){*itrxy *= scalar;}}RE *this;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN TableTypeForMA<T>& MA<Y,X,T>::RefTable() NE { RE m_M; }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN CO TableTypeForMA<T>& MA<Y,X,T>::GetTable() CO NE { RE m_M; }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN CO MA<Y,X,T>& MA<Y,X,T>::Unit() NE { static CO MA<Y,X,T> unit = Unit_Body(); RE unit; }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> MA<Y,X,T>::Unit_Body() NE{TableTypeForMA<T> M{};for( SizeTypeForMA y = 0 ; y < Y ; y++ ){LineTypeForMA<T> vec{};for( SizeTypeForMA x = 0 ; x < X ; x++ ){vec.push_back( x == y ? 1 : 0 );}M.push_back( vec );}RE MA<Y,X,T>( M );}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN void MA<Y,X,T>::COructTable( TableTypeForMA<T>& M , LineTypeForMA<T>& vec ) NE { M.push_back( vec ); vec.clear(); }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> TE <TY Arg , TY... Args> void MA<Y,X,T>::COructTable( TableTypeForMA<T>& M , LineTypeForMA<T>& vec , CO Arg& arg , CO Args&... args ) NE{vec.push_back( arg );if( vec.size() == X ){COructTable( M , vec );}if( M.size() < Y ){COructTable( M , vec , args... );}return;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T> OP==( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ) NE { RE mat1.GetTable() == mat2.GetTable(); }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T> IN MA<Y,X,T> OP!=( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ) NE { RE !( mat1 == mat2 ); }TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP+( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ){MA<Y,X,T> mat1_copy = mat1;mat1_copy += mat2;RE mat1_copy;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP-( CO MA<Y,X,T>& mat1 , CO MA<Y,X,T>& mat2 ){MA<Y,X,T> mat1_copy = mat1;mat1_copy -= mat2;RE mat1_copy;}TE <SizeTypeForMA Y , SizeTypeForMA X , SizeTypeForMA Z , TY T> IN MA<Y,Z,T> OP*( CO MA<Y,X,T>& mat1 , CO MA<X,Z,T>& mat2 ){CO TableTypeForMA<T>& M1 = mat1.GetTable();CO TableTypeForMA<T>& M2 = mat2.GetTable();TableTypeForMA<T> M_prod{};auto begin2x = M2.begin();for( auto itr1y = M1.begin() , end1y = M1.end() ; itr1y != end1y ; itr1y++ ){LineTypeForMA<T> vec{};auto begin1yx = itr1y->begin() , end1yx = itr1y->end();for( SizeTypeForMA z = 0 ; z < Z ; z++ ){auto itr1yx = begin1yx;auto itr2x = begin2x;T inner_product{};WH( itr1yx != end1yx ){inner_product += ( *itr1yx ) * ( *itr2x )[z];itr1yx++;itr2x++;}vec.push_back( inner_product );}M_prod.push_back( vec );}RE MA<Y,Z,T>( M_prod );}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<Y,X,T> OP*( CO T& scalar , CO MA<Y,X,T>& mat ){MA<Y,X,T> mat_copy = mat;mat_copy *= scalar;RE mat_copy;}TE <SizeTypeForMA Y , SizeTypeForMA X , TY T>MA<X,Y,T> Transpose( CO MA<Y,X,T>& mat ){CO TableTypeForMA<T>& M = mat.GetTable();TableTypeForMA<T> M_t{};auto beginy = M.begin();for( auto itr1x = beginy->begin() , end1x = beginy->end() ; itr1x != end1x ; itr1x++ ){M_t.push_back( LineTypeForMA<T>() );}for( auto itry = beginy , endy = M.end() ; itry != endy ; itry++ ){auto itryx = itry->begin() , endyx = itry->end();auto itr_ty = M_t.begin();WH( itryx != endyx ){itr_ty->push_back( *itryx );itryx++;itr_ty++;}}RE MA<X,Y,T>( M_t );}TE <SizeTypeForMA X , TY T>T Trace( CO MA<X,X,T>& mat ){int i = 0;T answer =0;CO TableTypeForMA<T>& M = mat.GetTable();for( auto itry = M.begin() , endy = M.end() ; itry != endy ; itry++ ){answer += ( *itry )[i];i++;}RE answer;}
int main()
{
UNTIE;
CEXPR( int , bound_T , 100000 );
CIN_ASSERT( T , 1 , bound_T );
CEXPR( ll , bound_N , 1000000000000000000 );
CEXPR( ll , bound_K1 , bound_T );
CEXPR( ll , bound_K2 , bound_N );
using MOD = Mod<P>;
using MODX = PO<MOD>;
using MODTX = TP<MOD>;
MOD zero{ 0 };
MOD one{ 1 };
MOD two{ 2 };
MOD two_inv{ ( P + 1 ) / 2 };
MODX X{ 1 , one };
if( false ){
CEXPR( int , bound_Kr , 407 ); 
CEXPR( int , bound_Kq , bound_K1 / bound_Kr + 1 );
static LI<ll> N[bound_Kq] = {};
static LI<ll> K[bound_Kq] = {};
int Kq[bound_T];
FOR( t , 0 , T ){
CIN_ASSERT( Nt , 1 , bound_N );
CIN_ASSERT( Kt , 0 , min( Nt * 2 , bound_K1 ) );
int& Kqt = Kq[t];
if( Kt >= P ){
Kqt = -1;
} else {
Kqt = Kt / bound_Kr;
N[Kqt].push_back( Nt );
K[Kqt].push_back( Kt );
}
}
static LI<MOD> answer[bound_Kq] = {};
} else {
CEXPR( ll , power_2_15 , 1 << 15 );
REPEAT( T ){
if(VARIABLE_FOR_REPEAT > 100000 ){
cout << "TLE!!!!\n";
} else {
CIN_ASSERT( N , 1 , bound_N );
CIN_ASSERT( K , 0 , min( N * 2 , bound_K2 ) );
// if( K >= P ){
// cout << 0 << "\n";
if( K >= 100000 ){
cout << "TLE!!!!\n";
} else {
ll Kq = K / power_2_15;
MA<2,2,MODX> MNX
{
X * ( -two ) + two * N , X * ( - X + two * N + one ) * two_inv ,
one , zero
};
LI<MOD> point{};
FOR( k , Kq * power_2_15 , K ){
point.push_back( k );
}
LI<LI<MODTX> > point_tree{};
SetPointTree( point , point_tree );
LI<MOD> MN[2][2] = {};
FOR( i , 0 , 2 ){
VE<MODX>& MNXi = MNX.m_M[i];
LI<MOD> ( &MNi )[2] = MN[i];
FOR( j , 0 , 2 ){
SetMultipointEvaluation( MNXi[j] , point_tree , MNi[j] );
}
}
MA<2,1,MOD> v{
one , 
zero
};
if( Kq > 0 ){
MOD power_2{ one };
FOR( i , 0 , 15 ){
VE<MODX>& MNX0 = MNX.m_M[0];
VE<MODX>& MNX1 = MNX.m_M[1];
MNX = move( MNX * MA<2,2,MODX>
{
MNX0[0] << power_2 , MNX0[1] << power_2 ,
MNX1[0] << power_2 , MNX1[1] << power_2
} );
power_2 *= 2;
}
point.clear();
FOR( k , 0 , Kq ){
point.push_back( k * power_2_15 );
}
point_tree.clear();
SetPointTree( point , point_tree );
LI<MOD> L[2][2] = {};
FOR( i , 0 , 2 ){
VE<MODX>& MNXi = MNX.m_M[i];
LI<MOD> ( &Li )[2] = L[i];
FOR( j , 0 , 2 ){
SetMultipointEvaluation( MNXi[j] , point_tree , Li[j] );
}
}
LI<MOD> ( &L0 )[2] = L[0];
LI<MOD> ( &L1 )[2] = L[1];
LI<MOD>& L00 = L0[0];
LI<MOD>& L01 = L0[1];
LI<MOD>& L10 = L1[0];
LI<MOD>& L11 = L1[1];
WH( ! L00.empty() ){
v = move( MA<2,2,MOD>
(
L00.front() , L01.front() ,
L10.front() , L11.front()
)
* v );
L00.pop_front();
L01.pop_front();
L10.pop_front();
L11.pop_front();
}
}
LI<MOD> ( &MN0 )[2] = MN[0];
LI<MOD> ( &MN1 )[2] = MN[1];
LI<MOD>& MN00 = MN0[0];
LI<MOD>& MN01 = MN0[1];
LI<MOD>& MN10 = MN1[0];
LI<MOD>& MN11 = MN1[1];
WH( ! MN00.empty() ){
v = move( MA<2,2,MOD>
(
MN00.front() , MN01.front() ,
MN10.front() , MN11.front()
)
* v );
MN00.pop_front();
MN01.pop_front();
MN10.pop_front();
MN11.pop_front();
}
cout << v.m_M[0][0] << "\n";
}
}
}
}
QUIT;
}
yukicoder

結果

テストケース

ソースコード
