// #define _GLIBCXX_DEBUG 
// #include "Utility/Header.hpp"
// #include "Utility/String/a_Body.hpp"
// #include "Contest/Header.hpp"

// #include<bits/stdc++.h>
// using namespace std;

// using ll = long long;
// using uint = unsigned int;
// #include "Mathematics/Arithmetic/Prime/a_Body.hpp"


#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CIN( LL , A ) LL A; cin >> A 
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#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 REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

template <typename T> class TruncatedPolynomial;

template <typename T>
class Polynomial
{

  friend class TruncatedPolynomial<T>;

protected:
  vector<T> m_f;
  // m_fのsize
  uint m_size;
  bool m_no_redundant_zero;
  
public:
  inline Polynomial();
  inline Polynomial( const T& t );
  inline Polynomial( const Polynomial<T>& f );
  inline Polynomial( const uint& i , const T& t );
  inline Polynomial( vector<T>&& f );

  Polynomial<T>& operator=( const T& t );
  Polynomial<T>& operator=( const Polynomial<T>& f );

  inline const T& operator[]( const uint& i ) const;
  inline T& operator[]( const uint& i );

  inline Polynomial<T>& operator+=( const T& t );
  Polynomial<T>& operator+=( const Polynomial<T>& f );
  inline Polynomial<T>& operator-=( const T& t );
  Polynomial<T>& operator-=( const Polynomial<T>& f );
  Polynomial<T>& operator*=( const T& t );
  Polynomial<T>& operator*=( const Polynomial<T>& f );
  Polynomial<T>& operator/=( const T& t );
  Polynomial<T>& operator%=( const T& t );

  inline Polynomial<T> operator-() const;

  inline const vector<T>& GetCoefficient() const noexcept;
  inline const uint& size() const noexcept;
  
  void RemoveRedundantZero();

  inline string Display() const noexcept;
  
  static inline const Polynomial<T>& zero();
  static inline const T& const_zero();
  static inline const T& const_one();
  static inline const T& const_minus_one();

};

template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 );
template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 );
template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 );

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f );
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 );
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 );
template <typename T> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const T& t1 );

template <typename T> inline Polynomial<T>::Polynomial() : m_f() , m_size( 0 ) , m_no_redundant_zero( true ) {}
template <typename T> inline Polynomial<T>::Polynomial( const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( 0 ) = t; } }
template <typename T> inline Polynomial<T>::Polynomial( const Polynomial<T>& f ) : m_f( f.m_f ) , m_size( f.m_size ) , m_no_redundant_zero( f.m_no_redundant_zero ) {}
template <typename T> inline Polynomial<T>::Polynomial( const uint& i , const T& t ) : Polynomial() { if( t != const_zero() ){ operator[]( i ) = t; } }
template <typename T> inline Polynomial<T>::Polynomial( vector<T>&& f ) : m_f( move( f ) ) , m_size( m_f.size() ) , m_no_redundant_zero( false ) {}


template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const T& t ) { m_f.clear(); m_size = 0; operator[]( 0 ) = t; return *this; }
template <typename T> inline Polynomial<T>& Polynomial<T>::operator=( const Polynomial<T>& f ) { m_f = f.m_f; m_size = f.m_size; m_no_redundant_zero = f.m_no_redundant_zero; return *this; }


template <typename T>
const T& Polynomial<T>::operator[]( const uint& i ) const
{

  if( m_size <= i ){

    return const_zero();

  }
  
  return m_f[i];

}

template <typename T> inline T& Polynomial<T>::operator[]( const uint& i )
{

  m_no_redundant_zero = false;

  if( m_size <= i ){
    
    const T& z = const_zero();

    while( m_size <= i ){

      m_f.push_back( z );
      m_size++;
    
    }

  }

  return m_f[i];

}

template <typename T> inline Polynomial<T>& Polynomial<T>::operator+=( const T& t ) { operator[]( 0 ) += t; return *this; }

template <typename T>
Polynomial<T>& Polynomial<T>::operator+=( const Polynomial<T>& f )
{

  for( uint i = 0 ; i < f.m_size ; i++ ){

    operator[]( i ) += f.m_f[i];

  }

  return *this;

}

template <typename T> inline Polynomial<T>& Polynomial<T>::operator-=( const T& t ) { operator[]( 0 ) -= t; return *this; }

template <typename T>
Polynomial<T>& Polynomial<T>::operator-=( const Polynomial<T>& f )
{

  for( uint i = 0 ; i < f.m_size ; i++ ){

    operator[]( i ) -= f.m_f[i];

  }

  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator*=( const T& t )
{

  // Tが位数の小さい環である場合も扱う時は冗長な0が生じやすいので次のコメントアウトを解除する。
  // if( ! m_no_redundant_zero ){
    
  //   RemoveRedundantZero();

  // }

  if( m_size == 0 || t == const_one() ){

    return *this;

  }

  if( t == const_zero() ){

    return operator=( zero() );

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) *= t;

  }

  // Tが整域でない場合も扱う時は冗長な0が生じうるので次のコメントアウトを解除する。
  // RemoveRedundantZero();
  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator*=( const Polynomial<T>& f )
{
  
  // Tが位数の小さい環である場合も扱う時は冗長な0が生じやすいので次のコメントアウトを解除する。
  // if( ! m_no_redundant_zero ){
    
  //   RemoveRedundantZero();

  // }

  if( m_size == 0 ){

    return *this;

  }

  if( f.m_size == 0 ){

    return operator=( zero() );

  }
  
  const uint size = m_size + f.m_size - 1;
  Polynomial<T> product{};  
      
  for( uint i = 0 ; i < size ; i++ ){

    T& product_i = product[i];
    const uint j_min = m_size <= i ? i - m_size + 1 : 0;
    const 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];

    }

  }

  // Tが整域でない場合も扱う時は冗長な0が生じうるので次のコメントアウトを解除する。
  // product.RemoveRedundantZero();
  return operator=( product );

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator/=( const T& t )
{
  
  // Tが位数の小さい環である場合も扱う時は冗長な0が生じやすいので次のコメントアウトを解除する。
  // if( ! m_no_redundant_zero ){
    
  //   RemoveRedundantZero();

  // }

  if( t == const_one() ){

    return *this;

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) /= t;

  }

  // Tが体でない場合も扱う時は冗長な0が生じうるので次のコメントアウトを解除する。
  // RemoveRedundantZero();
  return *this;

}

template <typename T>
Polynomial<T>& Polynomial<T>::operator%=( const T& t )
{

  // Tが位数の小さい環である場合も扱う時は冗長な0が生じやすいので次のコメントアウトを解除する。
  // if( ! m_no_redundant_zero ){
    
  //   RemoveRedundantZero();

  // }

  if( t == const_one() ){

    return operator=( zero() );

  }
  
  for( uint i = 0 ; i < m_size ; i++ ){

    operator[]( i ) %= t;

  }

  // Tが位数の小さい環である場合も扱う時は冗長な0が生じやすいので次のコメントアウトを解除する。
  // RemoveRedundantZero();
  return *this;

}

template <typename T> inline Polynomial<T> Polynomial<T>::operator-() const { Polynomial<T>().operator-=( *this ); }

template <typename T> inline const vector<T>& Polynomial<T>::GetCoefficient() const noexcept { return m_f; }
template <typename T> inline const uint& Polynomial<T>::size() const noexcept { return m_size; }

template <typename T>
void Polynomial<T>::RemoveRedundantZero()
{

  if( m_no_redundant_zero ){
    
    return;

  }
  
  const T& z = const_zero();
  
  while( m_size > 0 ? m_f[m_size - 1] == z : false ){

    m_f.pop_back();
    m_size--;

  }

  m_no_redundant_zero = true;
  return;

}

template <typename T>
string Polynomial<T>::Display() const noexcept
{

  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 += ")";
  return s;

}


template <typename T> inline const Polynomial<T>& Polynomial<T>::zero() { static const Polynomial<T> z{}; return z; }
template <typename T> inline const T& Polynomial<T>::const_zero() { static const T z{ 0 }; return z; }
template <typename T> inline const T& Polynomial<T>::const_one() { static const T o{ 1 }; return o; }
template <typename T> inline const T& Polynomial<T>::const_minus_one() { static const T m{ -1 }; return m; }


template <typename T>
bool operator==( const Polynomial<T>& f0 , const T& t1 )
{

  const uint& size = f0.size();
  const T& zero = Polynomial<T>::const_zero();

  for( uint i = 1 ; i < size ; i++ ){

    if( f0[i] != zero ){

      return false;

    }

  }

  return f0[0] == t1;

}

template <typename T>
bool operator==( const Polynomial<T>& f0 , const Polynomial<T>& f1 )
{

  const uint& size0 = f0.size();
  const uint& size1 = f1.size();
  const uint& size = size0 < size1 ? size1 : size0;

  for( uint i = 0 ; i < size ; i++ ){

    if( f0[i] != f1[i] ){

      return false;

    }

  }

  return true;

}

template <typename T , typename P> inline bool operator!=( const Polynomial<T>& f0 , const P& f1 ) { return !( f0 == f1 ); }

template <typename T , typename P> inline Polynomial<T> operator+( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; f += f1; return f; }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f ) { return Polynomial<T>::zero() - f; }
template <typename T , typename P> inline Polynomial<T> operator-( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; return f.operator-=( f1 ); }
template <typename T , typename P> inline Polynomial<T> operator*( const Polynomial<T>& f0 , const P& f1 ) { Polynomial<T> f = f0; return f.operator*=( f1 ); }
template <typename T> inline Polynomial<T> operator/( const Polynomial<T>& f0 , const T& t1 ) { Polynomial<T> f = f0; return f.operator/=( t1 ); }
template <typename T> inline Polynomial<T> operator%( const Polynomial<T>& f0 , const T& t1 ) { Polynomial<T> f = f0; return f.operator%=( t1 ); }

#define RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION )	\
  if( CONDITION ){							\
									\
    return operator=( zero );						\
									\
  }									\
									\


#define RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( CONDITION ) \
  if( CONDITION ){							\
									\
    return TruncatedPolynomial<T>( m_N );				\
									\
  }									\
									\


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



#define SET_VECTOR_FOR_ANSWER_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( N_OUTPUT_LIM ) \
  vector<T> answer( N_OUTPUT_LIM )					\


#define SET_SUM_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL	\
  Polynomial<T>::m_f[i] = sum					\



#define SET_SUM_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL \
  answer[i] = sum						    \

#define SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_START_NUM ) \
  uint N_INPUT_START_NUM;						\
									\
  for( uint i = 0 ; i < SIZE && searching ; i++ ){			\
									\
    if( F[i] != zero ){							\
									\
      N_INPUT_START_NUM = i;						\
      searching = false;						\
									\
    }									\
									\
  }									\
									\


#define SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( F , SIZE , N_INPUT_MAX_NUM ) \
  uint N_INPUT_MAX_NUM;							\
  searching = true;							\
									\
  for( uint i = ( SIZE ) - 1 ; searching ; i-- ){			\
									\
    if( F[i] != zero ){							\
									\
      N_INPUT_MAX_NUM = i;						\
      searching = false;						\
									\
    }									\
									\
  }									\
									\


#define CONVOLUTION_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) \
  const 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 += Polynomial<T>::m_f[j] * f.Polynomial<T>::m_f[i - j];		\
									\
  }									\
									\
  Polynomial<T>::m_f[i] = sum;						\
									\


#define CONVOLUTION_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL( J_MIN ) \
  const 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 += Polynomial<T>::m_f[j] * f.Polynomial<T>::m_f[i - j];	\
									\
  }									\
									\



#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 )( Polynomial<T>::m_size == 0 ); \
  uint N_output_max = Polynomial<T>::m_size + f.Polynomial<T>::m_size - 2; \
									\
  if( N_output_max >= m_N ){						\
									\
    N_output_max = m_N - 1;						\
									\
  }									\
									\
  const uint N_output_lim = N_output_max + 1;				\
  CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim ); \
									\
  for( uint i = N_output_max ; searching ; i-- ){			\
									\
    T sum{ zero };							\
									\
    for( uint j = 0 ; j <= i ; j++ ){					\
									\
      sum += ACCESS_ENTRY * f.Polynomial<T>::operator[]( 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 , Polynomial<T>::m_f[j] ) \
									\
  

#define DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL	\
  DEFINITION_0_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST , Polynomial<T>::operator[]( j ) ) \
									\


#define DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) \
  SET_N_INPUT_START_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Polynomial<T>::m_f , Polynomial<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.Polynomial<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_CONST_FOR_TRUNCATED_POLYNOMIAL	\
  DEFINITION_1_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST )	\
									\
  

#define DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL		\
  SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( Polynomial<T>::m_f , Polynomial<T>::m_size , N_input_max_0 ); \
  SET_N_INPUT_MAX_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( f , f.Polynomial<T>::m_size < m_N ? f.Polynomial<T>::m_size : m_N , N_input_max_1 ); \
  const uint N_input_max_0_max_1 = N_input_max_0 + N_input_max_1;	\
  const uint N_input_start_0_start_1 = N_input_start_0 + N_input_start_1; \
									\
  

#define DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL	\
  DEFINITION_2_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL		\
									\


#define DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION ) \
  const uint N_input_start_0_max_1 = N_input_start_0 + N_input_max_1;	\
  const uint N_input_max_0_start_1 = N_input_max_0 + N_input_start_1;	\
  const uint N_output_max_fixed = N_output_lim_fixed - 1;		\
  CONNECT( CONNECT( SET_VECTOR_FOR_ANSWER_OF_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_output_lim_fixed ); \
  									\
  for( uint i = N_output_max_fixed ; i > N_input_start_0_max_1 ; i-- ){	\
									\
    CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( i - N_input_max_1 ); \
									\
  }									\
									\
  searching = true;							\
									\
  for( uint i = N_input_start_0_max_1 < N_output_max_fixed ? N_input_start_0_max_1 : N_output_max_fixed ; searching ; i-- ){ \
									\
    CONNECT( CONNECT( CONVOLUTION_FOR_ , MULTIPLICATION ) , _FOR_TRUNCATED_POLYNOMIAL )( N_input_start_0 ); \
    searching = i > N_input_start_0_start_1;				\
									\
  }									\
									\
									\



#define DEFINITION_3_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL \
  DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( MULTIPLICATION )	\
								\
 

#define DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL	\
  DEFINITION_3_OF__FOR_TRUNCATED_POLYNOMIAL( TRUNCATED_MULTIPLICATION_CONST )	\
									\
 

#define DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL		\
  uint two_power = FFT_Multiplication_border_1_2<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++;								\
									\
  }									\
									\
  vector<T> f0{ move( FFT<T>( Polynomial<T>::m_f , N_input_start_0 , N_input_max_0 + 1 , 0 , two_power , exponent ) ) }; \
  const vector<T> f1{ move( FFT<T>( f.Polynomial<T>::m_f , N_input_start_1 , N_input_max_1 + 1 , 0 , two_power , exponent ) ) }; \
  Break( __LINE__ );							\
  for( uint i = 0 ; i < two_power ; i++ ){				\
									\
    f0[i] *= f1[i];							\
									\
  }									\
									\




#define DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL	\
  DEFINITION_4_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL		\
									\
 


#define DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION ) \
  const uint& N = f.GetTruncation();					\
  uint power;								\
  uint power_2 = 1;							\
  TruncatedPolynomial< TYPE > f_inv{ power_2 , Polynomial< TYPE >::const_one() / f[0] }; \
									\
  while( power_2 < N ){							\
  									\
    power = power_2;							\
    power_2 *= 2;							\
    f_inv.SetTruncation( power_2 );					\
    RECURSION;								\
									\
  }									\
									\
  f_inv.SetTruncation( N );						\
  return f_inv								\
									\



#define DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , RECURSION )	\
  const uint& N = f.GetTruncation();					\
  uint power;								\
  uint power_2 = 1;							\
  TruncatedPolynomial< TYPE > f_exp{ power_2 , Polynomial< TYPE >::const_one() }; \
									\
  while( power_2 < N ){							\
    Break( __LINE__ );							\
    power = power_2;							\
    power_2 *= 2;							\
    f_exp.SetTruncation( power_2 );					\
    RECURSION;								\
									\
  }									\
									\
  f_exp.SetTruncation( N );						\
  return f_exp								\
									\


inline void Break( const uint& n ) {};

#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 ) \
  template <> constexpr const uint FFT_Multiplication_border_0< TYPE > = BORDER_0; \
  template <> constexpr const uint FFT_Multiplication_border_1< TYPE > = BORDER_1; \
  template <> constexpr const uint FFT_Multiplication_border_1_2< TYPE > = BORDER_1_2; \
  template <> constexpr const uint FFT_Multiplication_border_1_2_exponent< TYPE > = BORDER_1_2_EXPONENT; \
  template <> constexpr const uint FFT_Multiplication_border_1_2_inv< TYPE > = BORDER_1_2_INV; \
  template <> inline TruncatedPolynomial< TYPE >& TruncatedPolynomial< TYPE >::operator*=( const Polynomial< TYPE >& f ) { return TruncatedPolynomial< TYPE >::FFT_Multiplication( f ); } \
									\
  template <>								\
  TruncatedPolynomial< TYPE > Inverse( const TruncatedPolynomial< TYPE >& f ) \
  {									\
									\
    DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_inv.TruncatedMinus( f_inv.FFT_TruncatedMultiplication_const( f , power , power_2 ).FFT_TruncatedMultiplication( f_inv , power , power_2 ) , power , power_2 ) ); \
									\
  }									\
									\
  template <>								\
  TruncatedPolynomial< TYPE > Exp( const TruncatedPolynomial< TYPE >& f ) \
  {									\
									\
    DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( TYPE , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).FFT_TruncatedMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).FFT_TruncatedMultiplication( f_exp , power , power_2 ) , power , power_2 ) ); \
									\
  }									\
									\
template <typename T> class TruncatedPolynomial;

template <typename T> TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );
template <typename T> TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start );

template <typename T>
class TruncatedPolynomial :
  public Polynomial<T>
{

  friend TruncatedPolynomial<T> TruncatedDifferential<T>( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );
  friend TruncatedPolynomial<T> TruncatedIntegral<T>( const TruncatedPolynomial<T>& f , const uint& N_output_start );
  
private:
  // m_N == 0でも動くが、その場合はm_size == 1の時にm_size <= m_Nが成り立たなくなることに注意
  uint m_N;
  
public:
  inline TruncatedPolynomial( const uint& N = 0 );
  inline TruncatedPolynomial( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial( const uint& N , const T& t );
  TruncatedPolynomial( const uint& N , const Polynomial<T>& f );
  inline TruncatedPolynomial( const uint& N , const uint& i , const T& t );
  inline TruncatedPolynomial( const uint& N , vector<T>&& f );

  // m_Nも代入されることに注意
  inline TruncatedPolynomial<T>& operator=( const TruncatedPolynomial<T>& f );
  inline TruncatedPolynomial<T>& operator=( const T& t );
  inline TruncatedPolynomial<T>& operator=( const Polynomial<T>& f );

  // m_Nは変化しないことに注意
  inline TruncatedPolynomial<T>& operator+=( const T& t );
  inline TruncatedPolynomial<T>& operator+=( const Polynomial<T>& f );

  // N_input_lim <= f.size()の場合のみサポート。
  // 自身を(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)を足した値 mod X^{ m_N }で置き換える。
  TruncatedPolynomial<T>& TruncatedPlus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_limit );

  inline TruncatedPolynomial<T>& operator-=( const T& t );
  inline TruncatedPolynomial<T>& operator-=( const Polynomial<T>& f );

  // N_input_lim <= f.size()の場合のみサポート。
  // 自身を(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)を引いた値 mod X^{ m_N }で置き換える。
  TruncatedPolynomial<T>& TruncatedMinus( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_limit );

  inline TruncatedPolynomial<T>& operator*=( const T& t );

  // m_N > 0の場合のみサポート。
  TruncatedPolynomial<T>& operator*=( const Polynomial<T>& f );

  // m_N > 0の場合のみサポート。
  // 自身をFFTによりf倍 mod X ^ { m_N }を計算した値で置き換える。
  // TruncatedPolynomial<T>& FFT_Multiplication( const Polynomial<T>& f );

  // m_N > 0かつf != 0の場合のみサポート。
  // 自身を(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)倍した値 mod X^{ m_N }で置き換える。
  TruncatedPolynomial<T>& TruncatedMultiplication( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_lim );
    
  // m_N > 0かつf != 0の場合のみサポート。
  // 自身をFFTにより(N_input_start個の0,f[N_input_start],...,f[N_input_lim-1],0,...)倍した値 mod X^{ m_N }で置き換える。
  // TruncatedPolynomial<T>& FFT_TruncatedMultiplication( const Polynomial<T>& f , const uint& N_input_start , const uint& N_input_lim );

  // m_N > 0の場合のみサポート。
  // 自身をf倍を計算した値をhとし、Polynomial<T>::m_fを長さm_Nの
  // (N_output_start個の0,h[N_output_start],...,h[N_output_lim - 1],0,...)
  // を返す。
  TruncatedPolynomial<T> TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const;

  // m_N > 0の場合のみサポート。
  // 自身をFFTによりf倍を計算した値をhとし、Polynomial<T>::m_fを長さm_Nの
  // (N_output_start個の0,h[N_output_start],...,h[N_output_lim - 1],0,...)
  // を返す。
  // TruncatedPolynomial<T> FFT_TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const;

  inline TruncatedPolynomial<T>& operator/=( const T& t );
  inline TruncatedPolynomial<T>& operator/=( const TruncatedPolynomial<T>& t );
  inline TruncatedPolynomial<T>& operator%=( const T& t );

  inline TruncatedPolynomial<T> operator-() const;

  inline void SetTruncation( const uint& N ) noexcept;
  inline const uint& GetTruncation() const noexcept;

  // N次未満を0に変更。
  inline TruncatedPolynomial<T>& TruncateInitial( const uint& N ) noexcept;
  // N次以上を0に変更。
  inline TruncatedPolynomial<T>& TruncateFinal( const uint& N ) noexcept;

};

// template <typename T> inline constexpr const uint FFT_Multiplication_border_0;
// template <typename T> inline constexpr const uint FFT_Multiplication_border_1;
// template <typename T> inline constexpr const uint FFT_Multiplication_border_1_2;
// template <typename T> inline constexpr const uint FFT_Multiplication_border_1_2_exponent;
// template <typename T> inline constexpr const uint FFT_Multiplication_border_1_2_inv;

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f );
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 );
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 );

// m_Nが1下がることに注意。
template <typename T> inline TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f );
// m_Nがi下がることに注意。
template <typename T> inline TruncatedPolynomial<T> Differential( const uint& i , const TruncatedPolynomial<T>& f );
// m_Nが1下がることに注意。
// N_output_start_plus_one > 0の場合のみサポート。
template <typename T> TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one );

// m_Nが1上がることに注意。
// Tが標数0またはf.m_N + 1以上の体の場合のみサポート。
template <typename T> inline TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f );
// m_Nが1上がることに注意。
// N_output_start > 0の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start );

// f[0]が可逆な場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 0の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。
template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f );

// Tが標数0またはf.m_N以上の体でかつf[0] == 1の場合のみサポート。
template <typename T>
TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t );

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N ) : Polynomial<T>() , m_N( N ) {}
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const TruncatedPolynomial<T>& f ) : Polynomial<T>( f ) , m_N( f.m_N ) {}
template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const T& t ) : Polynomial<T>( t ) , m_N( N ) {}

template <typename T>
TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const Polynomial<T>& f ) : Polynomial<T>() , m_N( N )
{

  const uint& size = f.Polynomial<T>::m_size < m_N ? f.Polynomial<T>::m_size : m_N;
  
  for( uint i = 0 ; i < size ; i++ ){

    Polynomial<T>::m_f.push_back( f.Polynomial<T>::m_f[i] );
    Polynomial<T>::m_size++;
    
  }

}

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , const uint& i , const T& t ) : Polynomial<T>() , m_N( N ) { if( i < m_N ? t != Polynomial<T>::const_zero() : false ){ Polynomial<T>::operator[]( i ) = t; } }

template <typename T> inline TruncatedPolynomial<T>::TruncatedPolynomial( const uint& N , vector<T>&& f ) : Polynomial<T>( move( f ) ) , m_N( N )
{

  while( Polynomial<T>::m_size > m_N ){

    Polynomial<T>::m_f.pop_back();
    Polynomial<T>::m_size--;

  }

}


template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const TruncatedPolynomial<T>& f ) { Polynomial<T>::operator=( f ); m_N = f.m_N; return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const T& t ) { Polynomial<T>::operator=( t ); return *this; }
template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator=( const Polynomial<T>& f ) { return operator=( TruncatedPolynomial<T>( m_N , f ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const T& t ) { Polynomial<T>::operator+=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator+=( const Polynomial<T>& f ) { return TruncatedPolynomial<T>::TruncatedPlus( f , 0 , f.Polynomial<T>::m_size ); }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedPlus( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_limit )
{

  const uint& size = N_output_limit < m_N ? N_output_limit < f.Polynomial<T>::m_size ? N_output_limit : f.Polynomial<T>::m_size : m_N < f.Polynomial<T>::m_size ? m_N : f.Polynomial<T>::m_size;
  const uint& size_min = Polynomial<T>::m_size < size ? Polynomial<T>::m_size : size;
  
  for( uint i = N_output_start ; i < size_min ; i++ ){

    Polynomial<T>::m_f[i] += f.Polynomial<T>::m_f[i];

  }

  for( uint i = Polynomial<T>::m_size ; i < size ; i++ ){
    
    Polynomial<T>::m_f.push_back( f.Polynomial<T>::m_f[i] );
    Polynomial<T>::m_size++;

  }

  return *this;

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const T& t ) { Polynomial<T>::operator-=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator-=( const Polynomial<T>& f ) { return TruncatedPolynomial<T>::TruncatedMinus( f , 0 , f.Polynomial<T>::m_size ); }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedMinus( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_limit )
{

  const uint& size = N_output_limit < m_N ? N_output_limit < f.Polynomial<T>::m_size ? N_output_limit : f.Polynomial<T>::m_size : m_N < f.Polynomial<T>::m_size ? m_N : f.Polynomial<T>::m_size;
  const uint& size_min = Polynomial<T>::m_size < size ? Polynomial<T>::m_size : size;
  
  for( uint i = N_output_start ; i < size_min ; i++ ){

    Polynomial<T>::m_f[i] -= f.Polynomial<T>::m_f[i];

  }

  for( uint i = Polynomial<T>::m_size ; i < size ; i++ ){

    Polynomial<T>::m_f.push_back( - f.Polynomial<T>::m_f[i] );
    Polynomial<T>::m_size++;

  }

  return *this;

}

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const T& t ) { Polynomial<T>::operator*=( t ); return *this; }

template <typename T>
TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator*=( const Polynomial<T>& f )
{

  constexpr const uint border_0 = 21;
  const T& zero = Polynomial<T>::const_zero();
  bool searching = true;

  if( Polynomial<T>::m_size < border_0 && f.Polynomial<T>::m_size < border_0 ){

    RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Polynomial<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;
    const 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;

  }

  return *this;

}

// template <typename T>
// TruncatedPolynomial<T>& TruncatedPolynomial<T>::FFT_Multiplication( const Polynomial<T>& f )
// {

//   constexpr const uint& border_0 = FFT_Multiplication_border_0<T>;
//   const T& zero = Polynomial<T>::const_zero();
//   bool searching = true;

//   if( Polynomial<T>::m_size < border_0 && f.Polynomial<T>::m_size < border_0 ){

//     RETURN_ZERO_FOR_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL_IF( f.Polynomial<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;
//     const 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 );
//     const uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;
//     constexpr const uint& 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;
//       Polynomial<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 ) );
//       Polynomial<T>::m_size = Polynomial<T>::m_f.size();

//     }

//   }
  
//   return *this;

// }

template <typename T> 
TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncatedMultiplication( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim )
{

  constexpr const uint border_0 = 21;
  const T& zero = Polynomial<T>::const_zero();
  bool searching = true;

  if( Polynomial<T>::m_size < border_0 && f.Polynomial<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;

  }

  return *this;

}

// template <typename T> 
// TruncatedPolynomial<T>& TruncatedPolynomial<T>::FFT_TruncatedMultiplication( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim )
// {

//   constexpr const uint& border_0 = FFT_Multiplication_border_0<T>;
//   const T& zero = Polynomial<T>::const_zero();
//   bool searching = true;

//   if( Polynomial<T>::m_size < border_0 && f.Polynomial<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 );
//     const uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;
//     constexpr const uint& 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;

//       }

//       const 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_VECTOR_FOR_ANSWER_OF_MULTIPLICATION_FOR_TRUNCATED_POLYNOMIAL( N_output_lim_fixed );

//       for( uint i = N_output_start ; i < N_output_lim_fixed ; i++ ){
    
// 	Polynomial<T>::m_f[i] = f0[i];

//       }

//     }

//   }

//   return *this;
  
// }

template <typename T> 
TruncatedPolynomial<T> TruncatedPolynomial<T>::TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const
{

  constexpr const uint border_0 = 21;
  const T& zero = Polynomial<T>::const_zero();
  bool searching = true;

  if( Polynomial<T>::m_size < border_0 && f.Polynomial<T>::m_size < border_0 ){

    DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
    return TruncatedPolynomial<T>( m_N , move( answer ) );
    
  }

  DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
  DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
  uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;

  if( N_output_lim_fixed > N_output_lim ){

    N_output_lim_fixed = N_output_lim;
    
  }
  
  RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );
  DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
  return TruncatedPolynomial<T>( m_N , move( answer ) );
  
}

// template <typename T> 
// TruncatedPolynomial<T> TruncatedPolynomial<T>::FFT_TruncatedMultiplication_const( const Polynomial<T>& f , const uint& N_output_start , const uint& N_output_lim ) const
// {

//   constexpr const uint& border_0 = FFT_Multiplication_border_0<T>;
//   const T& zero = Polynomial<T>::const_zero();
//   bool searching = true;

//   if( Polynomial<T>::m_size < border_0 && f.Polynomial<T>::m_size < border_0 ){

//     DEFINITION_0_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
//     return TruncatedPolynomial<T>( m_N , move( answer ) );
    
//   }

//   DEFINITION_1_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
//   DEFINITION_2_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
//   uint N_output_lim_fixed = N_input_max_0_max_1 < m_N ? N_input_max_0_max_1 + 1 : m_N;

//   if( N_output_lim_fixed > N_output_lim ){

//     N_output_lim_fixed = N_output_lim;
    
//   }
  
//   RETURN_ZERO_FOR_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL_IF( N_input_start_0_start_1 >= N_output_lim_fixed );
//   const uint N_input_truncated_deg_0_deg_1 = N_input_max_0 - N_input_start_0 + N_input_max_1 - N_input_start_1;
//   constexpr const uint& border_1 = FFT_Multiplication_border_1<T>;

//   if( N_input_truncated_deg_0_deg_1 < border_1 ){
    
//     DEFINITION_3_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
//     return TruncatedPolynomial<T>( m_N , move( answer ) );
    
//   }

//   DEFINITION_4_OF_TRUNCATED_MULTIPLICATION_CONST_FOR_TRUNCATED_POLYNOMIAL;
//   uint N_output_start_shifted;
//   uint N_output_shift_shifted;

//   if( N_output_start < N_input_start_0_start_1 ){

//     N_output_start_shifted = 0;
//     N_output_shift_shifted = N_input_start_0_start_1;

//   } else {
    
//     N_output_start_shifted = N_output_start - N_input_start_0_start_1;
//     N_output_shift_shifted = N_output_start;

//   }

//   const uint N_output_lim_shifted = N_output_lim_fixed - N_input_start_0_start_1;
//   return TruncatedPolynomial<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 ) ) );

// }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const T& t ) { Polynomial<T>::operator/=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator/=( const TruncatedPolynomial<T>& f ) { return operator*=( Inverse( m_N == f.m_N ? f : TruncatedPolynomial<T>( m_N , f ) ) ); }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::operator%=( const T& t ) { Polynomial<T>::operator%=( t ); return *this; }

template <typename T> inline TruncatedPolynomial<T> TruncatedPolynomial<T>::operator-() const { return TruncatedPolynomial<T>( m_N ).operator-=( *this ); }


template <typename T> inline void TruncatedPolynomial<T>::SetTruncation( const uint& N ) noexcept { m_N = N; TruncateFinal( m_N ); }
template <typename T> inline const uint& TruncatedPolynomial<T>::GetTruncation() const noexcept { return m_N; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncateInitial( const uint& N ) noexcept { const uint& size = N < Polynomial<T>::m_size ? N : Polynomial<T>::m_size; for( uint i = 0 ; i < size ; i++ ){ Polynomial<T>::m_f[i] = 0; } return *this; }

template <typename T> inline TruncatedPolynomial<T>& TruncatedPolynomial<T>::TruncateFinal( const uint& N ) noexcept { while( Polynomial<T>::m_size > N ){ Polynomial<T>::m_f.pop_back(); Polynomial<T>::m_size--; } return *this; }

template <typename T , typename P> inline TruncatedPolynomial<T> operator+( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return TruncatedPolynomial<T>( f0 ).operator+=( f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f ) { return TruncatedPolynomial<T>( f ).operator*=( Polynomial<T>::const_minus_one()); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator-( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return TruncatedPolynomial<T>( f0 ).operator-=( f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator*( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return TruncatedPolynomial<T>( f0 ).operator*=( f1 ); }
template <typename T , typename P> inline TruncatedPolynomial<T> operator/( const TruncatedPolynomial<T>& f0 , const P& f1 ) { return TruncatedPolynomial<T>( f0 ).operator*=( Inverse( f1 ) ); }
template <typename T> inline TruncatedPolynomial<T> operator%( const TruncatedPolynomial<T>& f0 , const T& t1 ) { return TruncatedPolynomial<T>( f0 ).operator%=( t1 ); }


template <typename T> inline TruncatedPolynomial<T> Differential( const TruncatedPolynomial<T>& f ) { return TruncatedDifferential<T>( f , 1 ); }

template <typename T> inline TruncatedPolynomial<T> Differential( const uint& i , const TruncatedPolynomial<T>& f ) { return i == 0 ? f : Differential<T>( i - 1 , Differential<T>( f ) ); }

template <typename T>
TruncatedPolynomial<T> TruncatedDifferential( const TruncatedPolynomial<T>& f , const uint& N_output_start_plus_one )
{

  if( f.m_N == 0 ){

    return TruncatedPolynomial<T>();

  }

  TruncatedPolynomial<T> f_dif{ f.m_N - 1 };

  if( N_output_start_plus_one < f.Polynomial<T>::m_size ){

    for( uint i = 1 ; i < N_output_start_plus_one ; i++ ){

      f_dif.Polynomial<T>::m_f.push_back( 0 );

    }

    for( uint i = N_output_start_plus_one ; i < f.Polynomial<T>::m_size ; i++ ){

      f_dif.Polynomial<T>::m_f.push_back( i * f.Polynomial<T>::m_f[i] );

    }

    f_dif.Polynomial<T>::m_size = f.Polynomial<T>::m_size - 1;

  }

  return f_dif;

}

template <typename T> inline TruncatedPolynomial<T> Integral( const TruncatedPolynomial<T>& f ) { return TruncatedIntegral<T>( f , 1 ); }

template <typename T>
TruncatedPolynomial<T> TruncatedIntegral( const TruncatedPolynomial<T>& f , const uint& N_output_start )
{

  TruncatedPolynomial<T> f_int{ f.m_N + 1 };

  if( N_output_start <= f.Polynomial<T>::m_size ){

    for( uint i = 0 ; i < N_output_start ; i++ ){

      f_int.Polynomial<T>::m_f.push_back( 0 );

    }

    for( uint i = N_output_start ; i <= f.Polynomial<T>::m_size ; i++ ){

      f_int.Polynomial<T>::m_f.push_back( f.Polynomial<T>::m_f[i - 1] / T( i ) );

    }

    f_int.Polynomial<T>::m_size = f.Polynomial<T>::m_size + 1;
    
  }

  return f_int;

}

template <typename T>
TruncatedPolynomial<T> Inverse( const TruncatedPolynomial<T>& f )
{

  DEFINITION_OF_INVERSE_FOR_TRUNCATED_POLYNOMIAL( T , f_inv.TruncatedMinus( f_inv.TruncatedMultiplication_const( f , power , power_2 ).TruncatedMultiplication( f_inv , power , power_2 ) , power , power_2 ) );
  
}

template <typename T>
TruncatedPolynomial<T> Exp( const TruncatedPolynomial<T>& f )
{

  DEFINITION_OF_EXP_FOR_TRUNCATED_POLYNOMIAL( T , f_exp.TruncatedMinus( ( TruncatedIntegral( Differential( f_exp ).TruncatedMultiplication_const( Inverse( f_exp ) , power - 1 , power_2 ) , power ).TruncatedMinus( f , power , power_2 ) ).TruncatedMultiplication( f_exp , power ) , power , power_2 ) );
  
}

template <typename T> inline TruncatedPolynomial<T> Log( const TruncatedPolynomial<T>& f ) { return Integral<T>( Differential<T>( f ) /= f ); }

template <typename T> inline TruncatedPolynomial<T> Power( const TruncatedPolynomial<T>& f , const T& t ) { return Exp( Log( f ) *= t ); }


int main()
{
  UNTIE;
  CIN( int , N );
  assert( 1 <= N && N <= 1000 );
  CIN( uint , I );
  assert( 1 <= I && I <= 1000 );
  using P1 = Polynomial<int>;
  using P2 = TruncatedPolynomial<P1>;
  I++;
  P2 f{ I , 1 };
  uint s;
  uint a;
  REPEAT( N ){
    cin >> s >> a;
    assert( 1 <= s && s <= 1000 );
    assert( 1 <= a && a <= 1000 );
    f = f * P2( I , s , P1( a , 1 ) ) + f;
  }
  uint a_max = 0;
  FOR( i , 0 , I ){
    const Polynomial<int>& fi = f[i];
    uint size = fi.size();
    if( size != 0 ){
      size--;
      if( a_max < size ){
	a_max = size;
      }
    }
  }
  RETURN( a_max );  
}