#793075 (C++17) No.2058 Binary String

提出ソース
結果

問題	No.2058 Binary String
ユーザー	👑 p-adic
提出日時	2022-08-26 22:50:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	61 ms / 2,000 ms
コード長	64,076 bytes
コンパイル時間	3,278 ms
コンパイル使用メモリ	215,572 KB
実行使用メモリ	23,652 KB
最終ジャッジ日時	2024-04-22 00:54:33
合計ジャッジ時間	4,078 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	47 ms 23,628 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	5 ms 5,376 KB
testcase_07	AC	55 ms 21,580 KB
testcase_08	AC	10 ms 6,552 KB
testcase_09	AC	57 ms 22,224 KB
testcase_10	AC	23 ms 10,828 KB
testcase_11	AC	14 ms 7,752 KB
testcase_12	AC	34 ms 14,536 KB
testcase_13	AC	27 ms 12,748 KB
testcase_14	AC	17 ms 8,908 KB
testcase_15	AC	16 ms 8,776 KB
testcase_16	AC	20 ms 10,444 KB
testcase_17	AC	25 ms 11,468 KB
testcase_18	AC	3 ms 5,376 KB
testcase_19	AC	60 ms 22,856 KB
testcase_20	AC	47 ms 18,636 KB
testcase_21	AC	59 ms 23,496 KB
testcase_22	AC	60 ms 23,504 KB
testcase_23	AC	61 ms 23,652 KB
testcase_24	AC	61 ms 23,500 KB
testcase_25	AC	61 ms 23,628 KB
権限があれば一括ダウンロードができます
ソースコード

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

using uint = unsigned int;
using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }

// 自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
using uint = unsigned int;
template <typename T> class VLArray;
template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;

template <typename T>
class EntryOfVLArray
{

  friend VLArray<T>;
  friend IteratorOfVLArray<T>;
  friend ConstIteratorOfVLArray<T>;

private:
  T m_t;
  EntryOfVLArray<T>* m_prev;
  EntryOfVLArray<T>* m_next;
  
private:
  inline EntryOfVLArray();
  template <typename Arg> inline EntryOfVLArray( const Arg& );
  template <typename Arg> inline EntryOfVLArray( const Arg& , EntryOfVLArray<T>* const& , EntryOfVLArray<T>* const& );

};

template <typename T> inline EntryOfVLArray<T>::EntryOfVLArray() : m_t() , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t ) : m_t( t ) , m_prev( this ) , m_next( this ) {}
template <typename T> template <typename Arg> inline EntryOfVLArray<T>::EntryOfVLArray( const Arg& t , EntryOfVLArray<T>* const& prev , EntryOfVLArray<T>* const& next ) : m_t( t ) , m_prev( prev ) , m_next( next ) {}

template <typename T> class EntryOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename T> class VLArray;

template <typename T>
class IteratorOfVLArray
{

  friend ConstIteratorOfVLArray<T>;
  friend VLArray<T>;

private:
  // ++の実装のためにはm_pをポインタへの参照にできない。
  EntryOfVLArray<T>* m_p;
  
public:
  inline IteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
  inline IteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;

  // inline T& Access() const;
  inline T& operator*() const;
  inline T* operator->() const;
  IteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
  inline void operator++( int );
  inline void operator--( int );

};

template <typename T>
class ConstIteratorOfVLArray
{

  friend VLArray<T>;

private:
  const EntryOfVLArray<T>* m_p;
  
public:
  inline ConstIteratorOfVLArray( EntryOfVLArray<T>* const& ) noexcept;
  inline ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& ) noexcept;
  inline ConstIteratorOfVLArray( const IteratorOfVLArray<T>& ) noexcept;

  inline const T& operator*() const;
  inline const T* operator->() const;
  ConstIteratorOfVLArray<T>& operator=( const ConstIteratorOfVLArray<T>& ) noexcept;
  ConstIteratorOfVLArray<T>& operator=( const IteratorOfVLArray<T>& ) noexcept;
  inline void operator++( int );
  inline void operator--( int );
  
  static inline bool Equal( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
  static inline bool Equal( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

};

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const IteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& , const ConstIteratorOfVLArray<T>& ) noexcept;

// IteratorOfVLArray
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline IteratorOfVLArray<T>::IteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}

// template <typename T> inline T& IteratorOfVLArray<T>::Access() const { return Access( m_p ).m_t; }
template <typename T> inline T& IteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; }
template <typename T> inline T* IteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }

template <typename T>
IteratorOfVLArray<T>& IteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;
  
}

template <typename T> inline void IteratorOfVLArray<T>::operator++( int ){ m_p = ( *m_p ).m_next; }
template <typename T> inline void IteratorOfVLArray<T>::operator--( int ){ m_p = ( *m_p ).m_prev; }

// ConstIteratorOfVLArray
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( EntryOfVLArray<T>* const& p ) noexcept : m_p( p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const ConstIteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}
template <typename T> inline ConstIteratorOfVLArray<T>::ConstIteratorOfVLArray( const IteratorOfVLArray<T>& itr ) noexcept : m_p( itr.m_p ) {}

template <typename T> inline const T& ConstIteratorOfVLArray<T>::operator*() const { return ( *m_p ).m_t; };
template <typename T> inline const T* ConstIteratorOfVLArray<T>::operator->() const { return &( *( *this ) ); }

template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const ConstIteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;

}

template <typename T>
ConstIteratorOfVLArray<T>& ConstIteratorOfVLArray<T>::operator=( const IteratorOfVLArray<T>& itr ) noexcept
{

  m_p = itr.m_p;
  return *this;

}

template <typename T> inline void ConstIteratorOfVLArray<T>::operator++( int ) { m_p = ( *m_p ).m_next; }
template <typename T> inline void ConstIteratorOfVLArray<T>::operator--( int ) { m_p = ( *m_p ).m_prev; }

template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }
template <typename T> inline bool ConstIteratorOfVLArray<T>::Equal( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return itr0.m_p == itr1.m_p; }

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const IteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const IteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T> inline bool operator==( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return ConstIteratorOfVLArray<T>::Equal( itr0 , itr1 ); }
template <typename T> inline bool operator!=( const ConstIteratorOfVLArray<T>& itr0 , const ConstIteratorOfVLArray<T>& itr1 ) noexcept { return !( itr0 == itr1 );}

template <typename T>
class SingletonType
{

protected:
  SingletonType() = default;
  SingletonType( const SingletonType& ) = default;
  virtual ~SingletonType() = default;
  SingletonType& operator=( const SingletonType& ) = default;

public:
  static T& GetUniqueObject();
  
};

template <typename T>
class SingletonOf :
  public SingletonType<SingletonOf<T> >
{

  friend SingletonType<SingletonOf<T> >;

private:
  SingletonOf() = default;
  SingletonOf( const SingletonOf& ) = default;
  ~SingletonOf() = default;
  SingletonOf& operator=( const SingletonOf& ) = default;

public:
  using type = T;

};

// Replace TYPE_NAME by a suitable typename.
/*
class TYPE_NAME :
  public SingletonType<TYPE_NAME>
{

  friend SingletonType<TYPE_NAME>;

private:
  TYPE_NAME() = default;
  TYPE_NAME( const TYPE_NAME& ) = default;
  ~TYPE_NAME() = default;
  TYPE_NAME& operator=( const TYPE_NAME& ) = default;

};
*/

template <typename T> T& Object();

#include <typeinfo>

template <typename T>
T& SingletonType<T>::GetUniqueObject()
{

    static T t;
    return t;

}

template <typename T>
T& Object()
{

  // if( ! is_base_of<SingletonType<T>,T>::value ){

  //   ERR_IMPUT( typeid( T ) );
    
  // }

  return T::GetUniqueObject();

}


template <int i>
class WrappedInt :
  public SingletonType<WrappedInt<i> >
{
  
  friend class SingletonType<WrappedInt<i> >;

private:
  WrappedInt() = default;
  WrappedInt( const WrappedInt& ) = default;
  WrappedInt& operator=( const WrappedInt& ) = default;
  static const int m_i;

public:
  static int Get();

};

template <uint i>
class WrappedUInt :
  public SingletonType<WrappedUInt<i> >
{

  friend class SingletonType<WrappedUInt<i> >;

private:
  WrappedUInt() = default;
  WrappedUInt( const WrappedUInt& ) = default;
  WrappedUInt& operator=( const WrappedUInt& ) = default;
  static const uint m_i;

public:
  static uint Get();

};

template <int i> const WrappedInt<i>& Wrap();
template <uint i> const WrappedUInt<i>& WrapU();


template <int i>
const int WrappedInt<i>::m_i = i;

template <uint i>
const uint WrappedUInt<i>::m_i = i;

template <int i>
int WrappedInt<i>::Get()
{

  return m_i;

}

template <uint i>
uint WrappedUInt<i>::Get()
{

  return m_i;

}

template <int i>
const WrappedInt<i>& Wrap()
{

  return Object<WrappedInt<i> >();

}

template <uint i>
const WrappedUInt<i>& WrapU()
{

  return Object<WrappedUInt<i> >();

}


class EmptySet
{

private:
  EmptySet();
  EmptySet( const EmptySet& );
  EmptySet& operator=( const EmptySet& );

};


template <typename T> class VLArray;

template <typename N , typename T> class VLMatrix_Body;

template <typename T>
class VLMatrix_Body<WrappedUInt<1>,T>
{

public:
  using type = VLArray<T>;

};

template <typename T>
class VLMatrix_Body<WrappedUInt<2>,T>
{

public:
  using type = VLArray<typename VLMatrix_Body<WrappedUInt<1>,T>::type>;

};

template <typename T>
class VLMatrix_Body<WrappedUInt<3>,T>
{

public:
  using type = VLArray<typename VLMatrix_Body<WrappedUInt<2>,T>::type>;

};

template <uint N , typename T>
using VLMatrix = typename VLMatrix_Body<WrappedUInt<N>,T>::type;


template <typename T> class IteratorOfVLArray;
template <typename T> class ConstIteratorOfVLArray;
template <typename Arg> class WrappedType;

template <typename T>
class VLArray
{

private:
  EntryOfVLArray<T> m_e;
  EntryOfVLArray<T>* const m_p_e;
  uint m_size;
  
public:
  // Tは引数0のコンストラクタを持つクラスのみ許容。
  inline VLArray();
  template <typename Arg1 , typename... Arg2> inline VLArray( const Arg1& , const Arg2&... );
  inline VLArray( const VLArray<T>& );

  // Tが引数0のコンストラクタを持たないクラスの場合に使用。
  template <typename Arg> inline VLArray( const WrappedType<Arg>& t );
  
  virtual ~VLArray();
  
  VLArray<T>& operator=( const VLArray<T>& );
  
  inline const uint& size() const noexcept;
  inline void clear();
  inline bool empty() const noexcept;
  T& front();
  const T& front() const;
  T& back();
  const T& back() const;
  
  template <typename Arg> void push_back( const Arg& );
  template <typename... Args> void push_back( const Args&... );
  template <typename Arg> void push_front( const Arg& );
  // 前から順にpush_frontする。
  template <typename... Args> void push_front( const Args&... );
  void pop_back();
  void pop_front();

  template <typename... Args> inline void Concatenate( const Args&... );
  template <typename Arg> void Concatenate_back( const Arg& );
  template <typename... Args> void Concatenate_back( const Args&... );
  template <typename Arg> void Concatenate_front( const Arg& );
  // 前から順にConcatenate_frontする。
  template <typename... Args> void Concatenate_front( const Args&... );

  using iterator = IteratorOfVLArray<T>;
  using const_iterator = ConstIteratorOfVLArray<T>;

  // *thisがconstである場合に確実にconst_iterator返しをするために、iterator返しは非constにする必要がある。
  inline iterator begin() noexcept;
  inline const_iterator begin() const noexcept;
  inline iterator end() noexcept;
  inline const_iterator end() const noexcept;
  template <typename Arg> void insert( const iterator& , const Arg& );
  template <typename Arg> void insert_front( const iterator& , const Arg& );
  template <typename Arg> void insert_back( const iterator& , const Arg& );
  iterator erase( iterator& );
  iterator erase_back( iterator& );
  iterator erase_front( iterator& );

  T& operator[]( const uint& );
  const T& operator[]( const uint& ) const;
  VLArray<T> GetInitialSegment( const int& ) const;
  VLArray<T> GetFinalSegment( const int& ) const;

  bool CheckContain( const iterator& ) const noexcept;
  bool CheckContain( const const_iterator& ) const noexcept;

  string Display() const;

private:
  template <typename Arg> inline int push_back_int( const Arg& );
  template <typename Arg> inline int push_front_int( const Arg& );
  template <typename Arg> inline int Concatenate_back_int( const Arg& );
  template <typename Arg> inline int Concatenate_front_int( const Arg& );

  template <typename... Args> static inline void ExpandParameterPack( const Args&... ) noexcept;

};


template <typename T> bool operator==( const VLArray<T>& , const VLArray<T>& );
template <typename T> inline bool operator!=( const VLArray<T>& , const VLArray<T>& );

template <typename T> VLArray<T> to_VLArray( const uint& , const T& );
template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& , const T& );
template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& , const uint& , const T& );
template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& , const uint& , const uint& , const T& );

template <typename T , typename... Arg> VLArray<T> Frown( const Arg&... );
template <typename T> T Sum( const VLArray<T>& );


template <typename Arg>
class WrappedType
{

private:
  Arg m_t;

public:
  template <typename... ARGS> inline WrappedType( const ARGS&... args );
  inline void Set( const Arg& t );
  inline const Arg& Get() const noexcept;

};

template <typename... Types>
class WrappedTypes
{};

template <typename Arg> template <typename... ARGS> inline WrappedType<Arg>::WrappedType( const ARGS&... args ) : m_t( args... ) {}

template <typename Arg> inline void WrappedType<Arg>::Set( const Arg& t ){ m_t = t; }
template <typename Arg> inline const Arg& WrappedType<Arg>::Get() const noexcept { return m_t; }

template <typename T> inline VLArray<T>::VLArray() : m_e() , m_p_e( &m_e ) , m_size( 0 ) {}
template <typename T> template <typename Arg1 , typename... Arg2> inline VLArray<T>::VLArray( const Arg1& t0 , const Arg2&... t1 ) : VLArray() { push_back( t0 , t1... ); }
template <typename T> inline VLArray<T>::VLArray( const VLArray<T>& a ) : m_e( a.m_e.m_t ) , m_p_e( &m_e ) , m_size( 0 ) { Concatenate( a ); }
template <typename T> template <typename Arg> inline VLArray<T>::VLArray( const WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_e( &m_e ) , m_size( 0 ) {}

template <typename T> VLArray<T>::~VLArray() { clear(); }

template <typename T>
VLArray<T>& VLArray<T>::operator=( const VLArray<T>& a )
{

  if( this != &a ){
    
    clear();
    Concatenate( a );
  
  }

  return *this;

}

template <typename T> inline const uint& VLArray<T>::size() const noexcept { return m_size; }
template <typename T> inline void VLArray<T>::clear(){ while( m_size > 0 ) pop_back(); }
template <typename T> inline bool VLArray<T>::empty() const noexcept { return m_size == 0; }

template <typename T>
T& VLArray<T>::front()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }
  
  return m_e.m_next->m_t;

}

template <typename T>
const T& VLArray<T>::front() const
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_next->m_t;

}

template <typename T>
T& VLArray<T>::back()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_prev->m_t;

}

template <typename T>
const T& VLArray<T>::back() const
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  return m_e.m_prev->m_t;

}

template <typename T> template <typename Arg>
void VLArray<T>::push_back( const Arg& t )
{
  
  EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
  auto p = new EntryOfVLArray<T>( t , p_e_prev , m_p_e );
    
  m_e.m_prev = p;
  p_e_prev->m_next = p;
  
  m_size++;
  return;

}


template <typename T> template <typename... Args>
void VLArray<T>::push_back( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでbackではなくfrontを使う。
  ExpandParameterPack( copy.push_front_int( args )... );
  Concatenate_back( copy );
  return;
  
}

template <typename T> template <typename Arg> inline int VLArray<T>::push_back_int( const Arg& t ) { push_back( t ); return 0; }

template <typename T> template <typename Arg>
void VLArray<T>::push_front( const Arg& t )
{

  EntryOfVLArray<T>* p_b = m_e.m_next;
  auto p = new EntryOfVLArray<T>( t , m_p_e , p_b );
    
  p_b->m_prev = p;
  m_e.m_next = p;
  
  m_size++;
  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::push_front( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでfrontではなくbackを使う。
  ExpandParameterPack( copy.push_back_int( args )... );
  Concatenate_front( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::push_front_int( const Arg& t ) { push_front( t ); return 0; }

template <typename T>
void VLArray<T>::pop_back()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }
  
  EntryOfVLArray<T>* p_e_prev = m_e.m_prev;
  EntryOfVLArray<T>* p_e_prev_prev = p_e_prev->m_prev;

  m_e.m_prev = p_e_prev_prev;
  p_e_prev_prev->m_next = m_p_e;
  
  delete p_e_prev;
  m_size--;
  return;
  
}

template <typename T>
void VLArray<T>::pop_front()
{

  // if( m_size == 0 ){

  //   ERR_CALL;
    
  // }

  EntryOfVLArray<T>* p_b = m_e.m_next;
  EntryOfVLArray<T>* p_b_next = ( *p_b ).m_next;

  p_b_next->m_prev = m_p_e;
  m_e.m_next = p_b_next;
  
  delete p_b;  
  m_size--;
  return;
  
}

template <typename T> template <typename... Args> inline void VLArray<T>::Concatenate( const Args&... args ) { Concatenate_back( args... ); }

template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_back( const Arg& a )
{
  
  const EntryOfVLArray<T>* p = a.m_p_e;
  const uint& N = a.m_size;
    
  for( uint n = 0 ; n < N ; n++ ){

    p = p->m_next;
    push_back( p->m_t );

  }

  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_back( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでbackではなくfrontを使う。
  ExpandParameterPack( copy.Concatenate_front_int( args )... );
  Concatenate_back( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_back_int( const Arg& a ) { Concatenate( a ); return 0; }

template <typename T> template <typename Arg>
void VLArray<T>::Concatenate_front( const Arg& a )
{
  
  const EntryOfVLArray<T>* p = a.m_p_e;
  const uint& N = a.m_size;
    
  for( uint n = 0 ; n < N ; n++ ){

    p = p->m_prev;
    push_front( p->m_t );

  }

  return;

}

template <typename T> template <typename... Args>
void VLArray<T>::Concatenate_front( const Args&... args )
{

  VLArray<T> copy{};

  // 関数の処理は後ろからなのでfrontではなくbackを使う。
  ExpandParameterPack( copy.Concatenate_back_int( args )... );
  Concatenate_front( copy );
  return;

}

template <typename T> template <typename Arg> inline int VLArray<T>::Concatenate_front_int( const Arg& a ) { Concatenate_front( a ); return 0; }


template <typename T> inline typename VLArray<T>::iterator VLArray<T>::begin() noexcept { return IteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::begin() const noexcept { return ConstIteratorOfVLArray<T>( m_e.m_next ); }
template <typename T> inline typename VLArray<T>::iterator VLArray<T>::end() noexcept { return IteratorOfVLArray<T>( m_p_e ); }
template <typename T> inline typename VLArray<T>::const_iterator VLArray<T>::end() const noexcept { return ConstIteratorOfVLArray<T>( m_p_e ); }

template <typename T> template <typename Arg> inline void VLArray<T>::insert( const typename VLArray<T>::iterator& itr , const Arg& t ) { insert_back( itr , t ); }

template <typename T> template <typename Arg>
void VLArray<T>::insert_front( const typename VLArray<T>::iterator& itr , const Arg& t )
{

  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr , t );
    
  // }

  if( itr == begin() ){

    push_front( t );

  } else {

    EntryOfVLArray<T>* p1 = itr.m_p;
    EntryOfVLArray<T>* p0 = p1->m_prev;
    auto p = new EntryOfVLArray<T>( t , p0 , p1 );
  
    p0->m_next = p;
    p1->m_prev = p;
  
    m_size++;

  }
  
  return;

}

template <typename T> template <typename Arg>
void VLArray<T>::insert_back( const typename VLArray<T>::iterator& itr , const Arg& t )
{

  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr , t );
    
  // }
  
  EntryOfVLArray<T>* p0 = itr.m_p;
  EntryOfVLArray<T>* p1 = p0->m_next;
  auto p = new EntryOfVLArray<T>( t , p0 , p1 );
  
  p1->m_prev = p;
  p0->m_next = p;
  
  m_size++;
  return;

}

template <typename T> inline typename VLArray<T>::iterator VLArray<T>::erase( typename VLArray<T>::iterator& itr ) { return erase_back( itr ); }

template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_back( typename VLArray<T>::iterator& itr )
{
  
  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr );
    
  // }

  EntryOfVLArray<T>* p = itr.m_p;
  EntryOfVLArray<T>* p0 = p->m_prev;
  EntryOfVLArray<T>* p1 = p->m_next;
  
  p0->m_next = p1;
  p1->m_prev = p0;
  itr++;
  
  delete p;
  m_size--;
  return itr;

}

template <typename T>
typename VLArray<T>::iterator VLArray<T>::erase_front( typename VLArray<T>::iterator& itr )
{
  
  // if( ! CheckContain( itr ) ){

  //   ERR_IMPUT( itr );
    
  // }

  EntryOfVLArray<T>* p = itr.m_p;
  EntryOfVLArray<T>* p0 = p->m_prev;
  EntryOfVLArray<T>* p1 = p->m_next;
  
  p0->m_next = p1;
  p1->m_prev = p0;
  itr--;
  
  delete p;
  m_size--;
  return itr;

}

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

  // if( i >= m_size ){

  //   ERR_IMPUT( i );

  // }

  if( i < m_size / 2 ){

    EntryOfVLArray<T>* p = m_e.m_next;

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

      p = p->m_next;

    }

    return p->m_t;

  }

  EntryOfVLArray<T>* p = m_e.m_prev;

  for( uint n = m_size - 1 ; n > i ; n-- ){

    p = p->m_prev;

  }

  return p->m_t;

}

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

  // if( i >= m_size ){

  //   ERR_IMPUT( i );

  // }

  if( i < m_size / 2 ){

    EntryOfVLArray<T>* p = m_e.m_next;

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

      p = p->m_next;

    }

    return p->m_t;

  }

  EntryOfVLArray<T>* p = m_e.m_prev;

  for( uint n = m_size - 1 ; n > i ; n-- ){

    p = p->m_prev;

  }

  return p->m_t;

}

template <typename T>
VLArray<T> VLArray<T>::GetInitialSegment( const int& n ) const
{

  const int N = (int)m_size;
  int M;

  if( N <= n ){

    M = N;

  } else {
    
    if( 0 <= n ){

      M = n;
      
    } else {

      M = N + n;

    }

  }

  VLArray<T> b{};
  const_iterator itr = begin();

  for( int m = 1 ; m <= M ; m++ ){

    b.push_back( *itr );
    itr++;

  }

  return b;

}

template <typename T>
VLArray<T> VLArray<T>::GetFinalSegment( const int& n ) const
{

  const int N = (int)m_size;
  int M;

  if( N <= n ){

    M = N;

  } else {
    
    if( 0 <= n ){

      M = n;
      
    } else {

      M = N + n;

    }
  
  }

  VLArray<T> b{};
  const_iterator itr = end();

  for( int m = 1 ; m <= M ; m++ ){

    itr--;
    b.push_front( *itr );

  }

  return b;

}

template <typename T>
bool VLArray<T>::CheckContain( const iterator& itr ) const noexcept
{

  for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){

    if( itr == itr_b ){

      return true;

    }
    
  }

  return false;

}

template <typename T>
bool VLArray<T>::CheckContain( const const_iterator& itr ) const noexcept
{

  for( auto itr_b = begin() , itr_e = end() ; itr_b != itr_e ; itr_b++ ){

    if( itr == itr_b ){

      return true;

    }
    
  }

  return false;

}

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

  string s = "(";
  EntryOfVLArray<T>* p = m_p_e;
  
  for( uint n = 0 ; n < m_size ; n++ ){

    p = p->m_next;
    
    if( n > 0 ){

      s += ",";

    }
    
    s += to_string( p->m_t );

  }

  s += ")";

  return s;

}

template <typename T> template <typename... Args> inline void VLArray<T>::ExpandParameterPack( const Args&... ) noexcept {};

template <typename T>
bool operator==( const VLArray<T>& a1 , const VLArray<T>& a2 )
{

  auto itr1 = a1.begin();
  auto end1 = a1.end();
  auto itr2 = a2.begin();
  auto end2 = a2.end();

  while( itr1 != end1 && itr2 != end2 ){

    if( *itr1 != *itr2 ){

      return false;

    }

    itr1++;
    itr2++;

  }

  return ( itr1 == end1 ) && ( itr2 == end2 );

}

template <typename T> inline bool operator!=( const VLArray<T>& a1 , const VLArray<T>& a2 ) { return !( a1 == a2 ); }


template <typename T> VLArray<T> to_VLArray( const uint& N , const T& t )
{

  auto a = VLArray<T>();

  for( uint n = 0 ; n < N ; n++ ){

    a.push_back( t );

  }

  return a;
  
}

template <typename T> inline VLMatrix<1,T> to_VLMatrix( const uint& N , const T& t ){ return to_VLArray( N , t ); }

template <typename T> inline VLMatrix<2,T> to_VLMatrix( const uint& N0 , const uint& N1 , const T& t ){ return to_VLArray( N1 , to_VLArray( N0 , t ) ); }

template <typename T> inline VLMatrix<3,T> to_VLMatrix( const uint& N0 , const uint& N1 , const uint& N2 , const T& t){ return to_VLArray( N2 , to_VLMatrix( N0 , N1 , t ) ); }

template <typename T , typename... Arg>
VLArray<T> Frown( const Arg&... args )
{

  VLArray<T> a{};
  a.Concatenate( args... );
  return a;

}

template <typename T> T Sum( const VLArray<T>& a )
{
  
  T t{};
  for( auto itr = a.begin() , end = a.end() ; itr != end ; itr++ ){

    t += *itr;

  }

  return t;

}


template <typename INT>
INT Residue( const INT& M , const INT& n ) noexcept;

template <typename INT>
INT Residue( const INT& M , const INT& n ) noexcept
{

  if( M == 0 ){

    return 0;

  }

  const INT M_abs = ( M > 0 ? M : -M );

  if( n < 0 ){

    const INT n_abs = -n;
    const INT res = n_abs % M_abs;
    return res == 0 ? res : M_abs - res;

  }

  return n % M_abs;

}


using INT_TYPE_FOR_ADIC_INT = long long int;

template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH = 0>
class AdicInt
{

private:
  VLArray<INT_TYPE_FOR_ADIC_INT> m_expansion;
  INT_TYPE_FOR_ADIC_INT m_n;

public:
  inline AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept;

  inline const VLArray<INT_TYPE_FOR_ADIC_INT>& GetExpansion() const noexcept;
  inline const INT_TYPE_FOR_ADIC_INT& GetValue() const noexcept;

  static const VLArray<INT_TYPE_FOR_ADIC_INT>& Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept;

};

template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline AdicInt<P,LENGTH>::AdicInt( const INT_TYPE_FOR_ADIC_INT& n ) noexcept : m_expansion( Expand( n ) ) , m_n( n ) {}

template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::GetExpansion() const noexcept { return m_expansion; }
template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH> inline const INT_TYPE_FOR_ADIC_INT& AdicInt<P,LENGTH>::GetValue() const noexcept { return m_n; }

template <INT_TYPE_FOR_ADIC_INT P , INT_TYPE_FOR_ADIC_INT LENGTH>
const VLArray<INT_TYPE_FOR_ADIC_INT>& AdicInt<P,LENGTH>::Expand( const INT_TYPE_FOR_ADIC_INT& n ) noexcept
{

  static VLArray<INT_TYPE_FOR_ADIC_INT> memory_n{};
  static VLArray<VLArray<INT_TYPE_FOR_ADIC_INT> > memory_answer{};

  if( P == 0 ){

    // ダミー
    return memory_n;

  }

  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n ){

    if( *itr_n == n ){

      return *itr_answer;

    }

    itr_n++;
    itr_answer++;

  }

  INT_TYPE_FOR_ADIC_INT n_copy = n;
  VLArray<INT_TYPE_FOR_ADIC_INT> answer{};

  if( LENGTH == 0 ){
  
    for( INT_TYPE_FOR_ADIC_INT i = 0 ; n_copy != 0 ; i++ ){

      const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy );
      answer.push_back( d );
      n_copy -= d;
      n_copy /= P;

    }

  } else {

    for( INT_TYPE_FOR_ADIC_INT i = 0 ; i < LENGTH && n_copy != 0 ; i++ ){

      const INT_TYPE_FOR_ADIC_INT d = Residue<INT_TYPE_FOR_ADIC_INT>( P , n_copy );
      answer.push_back( d );
      n_copy -= d;
      n_copy /= P;

    }

  }

  memory_n.push_back( n );
  memory_answer.push_back( answer );
  return memory_answer.back();

}

// init * ( t ^ num )
template <typename T , typename UINT>
T Power( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true , const string& method = "normal" );

template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true );
template <typename T , typename UINT>
T PowerBinaryMethod( const T& t , const UINT& num , const T& init = 1 , const bool& for_right_multiplication = true );

// 単なる２乗だが、T次第ではオーバーロードしてより高速なものに置き換える
template <typename T> inline T Square( const T& t );

// PowerBinaryMetodの呼び出しは部分特殊化ではなくオーバーロードで処理できるようにするためにPowerBinaryMethod<T,UINT>とはしない。
template <typename T , typename UINT>
inline T Power( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication , const string& method ) { return method == "binary" ? PowerBinaryMethod( t , num , init , for_right_multiplication ) : PowerNormalMethod( t , num , init , for_right_multiplication ); }

template <typename T , typename UINT> inline T PowerNormalMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication ) { return num == 0 ? init : ( for_right_multiplication ? PowerNormalMethod( t , num - 1 , init ) * t : t * PowerNormalMethod( t , num - 1 , init ) ); }

template <typename T , typename UINT>
T PowerBinaryMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication )
{

  const VLArray<UINT>& num_binary = AdicInt<2>::Expand( num );
  T answer = init;
  T power = t;

  for( auto itr = num_binary.begin() , end = num_binary.end() ; itr != end ; itr++ ){

    if( *itr == 1 ){

      answer = for_right_multiplication ? answer * power : power * answer;

    }

    // 部分特殊化ではなくオーバーロードで処理できるようにするためにSquare<T>としない。
    power = Square( power );

  }

  return answer;

}

template <typename T> inline T Square( const T& t ) { return t * t; }

using INT_TYPE_FOR_MOD = long long int;

// ここをtempate <typename INT , INT M>などにしてしまうとoperator+などを呼び出す際に型推論に失敗する。整数型を変えたい時はINT_TYPE_FOR_MODの型エイリアスを変更する。
template <INT_TYPE_FOR_MOD M>
class Mod
{

protected:
  INT_TYPE_FOR_MOD m_n;
  INT_TYPE_FOR_MOD m_inv;

public:
  inline Mod() noexcept;
  inline Mod( const INT_TYPE_FOR_MOD& n ) noexcept;
  inline Mod( const Mod<M>& n ) noexcept;
  inline Mod<M>& operator=( const INT_TYPE_FOR_MOD& n ) noexcept;
  Mod<M>& operator=( const Mod<M>& n ) noexcept;
  Mod<M>& operator+=( const INT_TYPE_FOR_MOD& n ) noexcept;
  inline Mod<M>& operator+=( const Mod<M>& n ) noexcept;
  inline Mod<M>& operator-=( const INT_TYPE_FOR_MOD& n ) noexcept;
  inline Mod<M>& operator-=( const Mod<M>& n ) noexcept;
  Mod<M>& operator*=( const INT_TYPE_FOR_MOD& n ) noexcept;
  Mod<M>& operator*=( const Mod<M>& n ) noexcept;

  // INT_TYPE_FOR_MODでの割り算ではないことに注意
  virtual Mod<M>& operator/=( const INT_TYPE_FOR_MOD& n );
  virtual Mod<M>& operator/=( const Mod<M>& n );
  
  Mod<M>& operator%=( const INT_TYPE_FOR_MOD& n );
  inline Mod<M>& operator%=( const Mod<M>& n );

  // 前置++/--を使うつもりがないので後置++/--と同じものとして定義する
  inline Mod<M>& operator++() noexcept;
  inline Mod<M>& operator++( int ) noexcept;
  inline Mod<M>& operator--() noexcept;
  inline Mod<M>& operator--( int ) noexcept;
  
  inline const INT_TYPE_FOR_MOD& Represent() const noexcept;
  void Invert() noexcept;
  bool CheckInvertible() noexcept;
  bool IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept;
  bool IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept;

};

template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;

template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept;
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 );
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 );
template <INT_TYPE_FOR_MOD M> Mod<M> Inverse( const Mod<M>& n );

template <INT_TYPE_FOR_MOD M> Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method = "normal" );

template <> inline Mod<2> Power( const Mod<2>& n , const INT_TYPE_FOR_MOD& p , const string& method );

// M乗が1になるよう定義されていることに注意
template <INT_TYPE_FOR_MOD M> inline Mod<M> Power( const Mod<M>& n , const Mod<M>& p , const string& method = "normal" );

template <> inline Mod<2> Power( const Mod<2>& n , const Mod<2>& p , const string& method );

// ../Power/a_Body.hppにて定義
template <typename T> inline T Square( const T& t );
template <> inline Mod<2> Square<Mod<2> >( const Mod<2>& t );

void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m );


template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod() noexcept : m_n( 0 ) , m_inv( M ){}

template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const INT_TYPE_FOR_MOD& n ) noexcept : m_n( Residue<INT_TYPE_FOR_MOD>( M , n ) ) , m_inv( 0 ){}

template <INT_TYPE_FOR_MOD M> inline Mod<M>::Mod( const Mod<M>& n ) noexcept : m_n( n.m_n ) , m_inv( 0 ){}

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator=( Mod<M>( n ) ); }

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator=( const Mod<M>& n ) noexcept
{

  m_n = n.m_n;
  m_inv = n.m_inv;
  return *this;

}

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator+=( const INT_TYPE_FOR_MOD& n ) noexcept
{

  m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n + n );
  m_inv = 0;
  return *this;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator+=( const Mod<M>& n ) noexcept { return operator+=( n.m_n ); };

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const INT_TYPE_FOR_MOD& n ) noexcept { return operator+=( -n ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator-=( const Mod<M>& n ) noexcept { return operator-=( n.m_n ); }

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator*=( const INT_TYPE_FOR_MOD& n ) noexcept
{

  m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n );
  m_inv = 0;
  return *this;

}

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator*=( const Mod<M>& n ) noexcept
{

  m_n = Residue<INT_TYPE_FOR_MOD>( M , m_n * n.m_n );

  if( m_inv == 0 || n.m_inv == 0 ){

    m_inv = 0;
    
  } else if( m_inv == M || n.m_inv == M ){

    m_inv = M;
    
  } else {

    Residue<INT_TYPE_FOR_MOD>( M , m_inv * n.m_inv );

  }
  
  return *this;

}

// 仮想関数なのでinline指定しない。
template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator/=( const INT_TYPE_FOR_MOD& n )
{

  return operator/=( Mod<M>( n ) );

}

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator/=( const Mod<M>& n )
{
  
  return operator*=( Inverse( n ) );
  
}

template <INT_TYPE_FOR_MOD M>
Mod<M>& Mod<M>::operator%=( const INT_TYPE_FOR_MOD& n )
{

  m_n %= Residue<INT_TYPE_FOR_MOD>( M , n );
  m_inv = 0;
  return *this;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator%=( const Mod<M>& n ) { return operator%=( n.m_n ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++() noexcept { return operator+=( 1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator++( int ) noexcept { return operator++(); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--() noexcept { return operator-=( 1 ); }
template <INT_TYPE_FOR_MOD M> inline Mod<M>& Mod<M>::operator--( int ) noexcept { return operator-=(); }

template <INT_TYPE_FOR_MOD M> inline const INT_TYPE_FOR_MOD& Mod<M>::Represent() const noexcept { return m_n; }

template <INT_TYPE_FOR_MOD M>
void Mod<M>::Invert() noexcept
{

  if( CheckInvertible() ){

    INT_TYPE_FOR_MOD i = m_inv;
    m_inv = m_n;
    m_n = i;

  } else {

    // m_nがMになるのはここの処理に限るのでRepresent()の値を参照することで例外処理可能
    m_n = M;
    m_inv = M;

  }

  return;
  
}

template <INT_TYPE_FOR_MOD M>
bool Mod<M>::CheckInvertible() noexcept
{

  if( m_inv == 0 ){

    LazyEvaluationOfModularInverse( M , m_n , m_inv );

  }

  return m_inv != M;
  
}

template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsSmallerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n < Residue<INT_TYPE_FOR_MOD>( M , n ); }
template <INT_TYPE_FOR_MOD M> inline bool Mod<M>::IsBiggerThan( const INT_TYPE_FOR_MOD& n ) const noexcept { return m_n > Residue<INT_TYPE_FOR_MOD>( M , n ); }

template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 == Mod<M>( n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator==( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 ) == n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator==( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() == n1.Represent(); }

template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 == n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator!=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 == n1 ); }

template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0.IsSmallerThan( n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1.IsBiggerThan( n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0.Represent() < n1.Represent(); }

template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n1 < n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator<=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n1 < n0 ); }

template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n1 < n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator>( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; }
template <INT_TYPE_FOR_MOD M> inline bool operator>( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n1 < n0; }

template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return !( n0 < n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); }
template <INT_TYPE_FOR_MOD M> inline bool operator>=( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return !( n0 < n1 ); }

template <INT_TYPE_FOR_MOD M>
Mod<M> operator+( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept
{

  auto n = n0;
  n += n1;
  return n;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 + n0; }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator+( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 + n1.Represent(); }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { return n0 + ( -n1 ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return Mod<M>( n0 - n1.Represent() ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator-( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept { return n0 - n1.Represent(); }

template <INT_TYPE_FOR_MOD M>
Mod<M> operator*( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept
{

  auto n = n0;
  n *= n1;
  return n;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator*( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) noexcept { return n1 * n0; }

template <INT_TYPE_FOR_MOD M>
Mod<M> operator*( const Mod<M>& n0 , const Mod<M>& n1 ) noexcept
{

  auto n = n0;
  n *= n1;
  return n;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 ) { return n0 / Mod<M>( n1 ); }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator/( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) / n1; }

template <INT_TYPE_FOR_MOD M>
Mod<M> operator/( const Mod<M>& n0 , const Mod<M>& n1 )
{

  auto n = n0;
  n /= n1;
  return n;

}

template <INT_TYPE_FOR_MOD M>
Mod<M> operator%( const Mod<M>& n0 , const INT_TYPE_FOR_MOD& n1 )
{

  auto n = n0;
  n %= n1;
  return n;

}

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const INT_TYPE_FOR_MOD& n0 , const Mod<M>& n1 ) { return Mod<M>( n0 ) % n1.Represent(); }

template <INT_TYPE_FOR_MOD M> inline Mod<M> operator%( const Mod<M>& n0 , const Mod<M>& n1 ) { return n0 % n1.Represent(); }

template <INT_TYPE_FOR_MOD M>
Mod<M> Inverse( const Mod<M>& n )
{

  auto n_copy = n;
  n_copy.Invert();
  return n_copy;

}

template <INT_TYPE_FOR_MOD M>
Mod<M> Power( const Mod<M>& n , const INT_TYPE_FOR_MOD& p , const string& method )
{

  if( p >= 0 ){

    return Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p , 1 , true , true , method );

  }

  return Inverse( Power<M>( n , -p , method ) );

}

template <> inline Mod<2> Power( const Mod<2>& n , const INT_TYPE_FOR_MOD& p , const string& method ) { return p == 0 ? 1 : n; }

template <INT_TYPE_FOR_MOD M> inline Mod<M> Power( const Mod<M>& n , const Mod<M>& p , const string& method ) { return Power<Mod<M>,INT_TYPE_FOR_MOD>( n , p.Represent() , method ); }

template <> inline Mod<2> Power( const Mod<2>& n , const Mod<2>& p , const string& method ) { return p == 0 ? 1 : n; }

template <> inline Mod<2> Square<Mod<2> >( const Mod<2>& t ) { return t; }


void LazyEvaluationOfModularInverse( const INT_TYPE_FOR_MOD& M , const INT_TYPE_FOR_MOD& n , INT_TYPE_FOR_MOD& m )
{

  static VLArray<INT_TYPE_FOR_MOD> memory_M{};

  // vectorでなくVLArrayだと引数が小さい順に呼び出した時の計算量がO(1)からO(n)に跳ね上がってしまう。
  static VLArray<vector<INT_TYPE_FOR_MOD> > memory_inverse{};

  auto itr_M = memory_M.begin() , end_M = memory_M.end();
  auto itr_inverse = memory_inverse.begin();

  vector<INT_TYPE_FOR_MOD>* p_inverse = nullptr;
  
  while( itr_M != end_M && p_inverse == nullptr ){

    if( *itr_M == M ){

      p_inverse = &( *itr_inverse );

    }

    itr_M++;
    itr_inverse++;

  }
  
  if( p_inverse == nullptr ){

    memory_M.push_front( M );
    memory_inverse.push_front( vector<INT_TYPE_FOR_MOD>() );
    p_inverse = &( memory_inverse.front() );
    p_inverse->push_back( M );

  }

  const INT_TYPE_FOR_MOD size = p_inverse->size();

  for( INT_TYPE_FOR_MOD i = size ; i <= n ; i++ ){

    p_inverse->push_back( 0 );

  }
  
  INT_TYPE_FOR_MOD& n_inv = ( *p_inverse )[n];

  if( n_inv != 0 ){

    m = n_inv;
    return;

  }

  const INT_TYPE_FOR_MOD M_abs = M >= 0 ? M : -M;
  const INT_TYPE_FOR_MOD n_sub = M_abs % n;
  INT_TYPE_FOR_MOD n_sub_inv = ( *p_inverse )[n_sub];

  if( n_sub_inv == 0 ){

    LazyEvaluationOfModularInverse( M , n_sub , n_sub_inv );

  }
  
  if( n_sub_inv != M ){

    n_inv = M_abs - ( ( n_sub_inv * ( M_abs / n ) ) % M_abs );
    m = n_inv;
    return;

  }
  
  for( INT_TYPE_FOR_MOD i = 1 ; i < M_abs ; i++ ){
    
    if( ( n * i ) % M_abs == 1 ){

      n_inv = i;
      m = n_inv;
      return;
      
    }

  }

  n_inv = M;
  m = n_inv;
  return;

}



// 階乗（INT = Mod<M>の時にMでの値が1であることに注意）
template <typename INT> inline INT Factorial( const INT& n , const INT& n_min = 1 , const string& mode = "normal" );

// modular階乗（INT1 = Mod<M>の時にMでの値が0であることに注意）
template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" );

// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min );

// ループ
template <typename INT1 , typename INT2>
INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min = 1 );

// modular階乗の逆数（INT1 = Mod<M>の時にMでの値がサポート外であることに注意）
template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min = 1 , const string& mode = "normal" );

// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min );
template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min );

// ループ
template <typename INT1 , typename INT2>
INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min = 1 );

// 場合の数
template <typename INT>
INT Combination( const INT& n , const INT& m , const string& mode = "normal" );

// 再帰式（呼び出し順によっては再帰深度が大きい）
template <typename INT>
const INT& CombinationNormalMethod( const INT& n , const INT& m );

// ループ（割り算回数が大きい）
template <typename INT>
INT CombinationLoopMethod( const INT& n , const INT& m );

// 階乗の比（modular演算でない時はオーバーフローしやすい）
template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m );
template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m );

template <typename INT> inline INT Factorial( const INT& n , const INT& n_min , const string& mode ) { return ModularFactorial<INT,INT>( n , n_min , mode ); }

template <typename INT1 , typename INT2> inline INT1 ModularFactorial( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialNormalMethod<INT1,INT2>( n , n_min ); }

template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n )
{

  // const参照返しなので静的const変数を返す。
  if( n < 1 ){

    static const INT1 one = 1;
    return one;

  }
  
  static VLArray<INT2> memory_n{};
  static VLArray<INT1> memory_answer{};
  
  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n ){

    if( *itr_n == n ){

      return *itr_answer;
      
    }

    itr_n++;
    itr_answer++;

  }

  const INT1 answer = n * ModularFactorialNormalMethod<INT1,INT2>( n - 1 );
  memory_n.push_front( n );
  memory_answer.push_front( answer );  
  return memory_answer.front();

}

template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod( const INT2& n , const INT2& n_min )
{

  if( n_min == 1 ){

    return ModularFactorialNormalMethod<INT1,INT2>( n );

  }

  return ModularFactorialNormalMethod_Body<INT1,INT2>( n , n_min );
  
}

template <typename INT1 , typename INT2>
const INT1& ModularFactorialNormalMethod_Body( const INT2& n , const INT2& n_min )
{
  
  // const参照返しなので静的const変数を返す。
  if( n < n_min ){

    static const INT1 one = 1;
    return one;

  }

  static VLArray<INT2> memory_n{};
  static VLArray<VLArray<INT2> > memory_n_min{};
  static VLArray<VLArray<INT1> > memory_answer{};
  VLArray<INT2>* p_n_min = nullptr;
  VLArray<INT1>* p_answer = nullptr;
  
  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_n_min = memory_n_min.begin();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n && p_n_min == nullptr ){

    if( *itr_n == n ){

      p_n_min = &( *itr_n_min );
      p_answer = &( *itr_answer );

    }

    itr_n++;
    itr_n_min++;
    itr_answer++;

  }

  if( p_n_min == nullptr ){

    memory_n.push_front( n );
    memory_n_min.push_front( VLArray<INT2>() );
    memory_answer.push_front( VLArray<INT1>() );
    p_n_min = &( memory_n_min.front() );
    p_answer = &( memory_answer.front() );

  }

  auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end();
  auto itr_answer_current = p_answer->begin();

  while( itr_n_min_current != end_n_min_current ){

    if( *itr_n_min_current == n_min ){

      return *itr_answer_current;

    }

    itr_n_min_current++;
    itr_answer_current++;

  }

  const INT1 answer = ModularFactorialNormalMethod<INT1,INT2>( n , n_min + 1 ) * n_min;
  p_n_min->push_front( n_min );
  p_answer->push_front( answer );  
  return p_answer->front();

}

template <typename INT1 , typename INT2>
INT1 ModularFactorialLoopMethod( const INT2& n , const INT2& n_min )
{

  INT1 f = 1;

  for( INT2 i = n_min ; i <= n ; i++ ){

    f *= i;

  }

  return f;

}

template <typename INT1 , typename INT2> inline INT1 ModularFactorialInverse( const INT2& n , const INT2& n_min , const string& mode ) { return mode == "loop" ? ModularFactorialInverseLoopMethod<INT1,INT2>( n , n_min ) : ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min ); }

template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n )
{

  // const参照返しなので静的const変数を返す。
  if( n < 1 ){

    static const INT1 one = 1;
    return one;

  }
  
  static VLArray<INT2> memory_n{};
  static VLArray<INT1> memory_answer{};

  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n ){

    if( *itr_n == n ){

      return *itr_answer;

    }

    itr_n++;
    itr_answer++;

  }

  const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n - 1 ) / n;
  memory_n.push_front( n );
  memory_answer.push_front( answer );  
  return memory_answer.front();

}

template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod( const INT2& n , const INT2& n_min )
{

  if( n_min == 1 ){

    return ModularFactorialInverseNormalMethod<INT1,INT2>( n );

  }

  return ModularFactorialInverseNormalMethod_Body<INT1,INT2>( n , n_min );

}

template <typename INT1 , typename INT2>
const INT1& ModularFactorialInverseNormalMethod_Body( const INT2& n , const INT2& n_min )
{
  
  // const参照返しなので静的const変数を返す。
  if( n < n_min ){

    static const INT1 one = 1;
    return one;

  }

  static VLArray<INT2> memory_n{};
  static VLArray<VLArray<INT2> > memory_n_min{};
  static VLArray<VLArray<INT1> > memory_answer{};
  VLArray<INT2>* p_n_min = nullptr;
  VLArray<INT1>* p_answer = nullptr;
  
  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_n_min = memory_n_min.begin();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n && p_n_min == nullptr ){

    if( *itr_n == n ){

      p_n_min = &( *itr_n_min );
      p_answer = &( *itr_answer );

    }

    itr_n++;
    itr_n_min++;
    itr_answer++;

  }

  if( p_n_min == nullptr ){

    memory_n.push_front( n );
    memory_n_min.push_front( VLArray<INT2>() );
    memory_answer.push_front( VLArray<INT1>() );
    p_n_min = &( memory_n_min.front() );
    p_answer = &( memory_answer.front() );

  }

  auto itr_n_min_current = p_n_min->begin() , end_n_min_current = p_n_min->end();
  auto itr_answer_current = p_answer->begin();

  while( itr_n_min_current != end_n_min_current ){

    if( *itr_n_min_current == n_min ){

      return *itr_answer_current;

    }

    itr_n_min_current++;
    itr_answer_current++;

  }

  const INT1 answer = ModularFactorialInverseNormalMethod<INT1,INT2>( n , n_min + 1 ) / (INT1)n_min;
  p_n_min->push_front( n_min );
  p_answer->push_front( answer );  
  return p_answer->front();

}

template <typename INT1 , typename INT2>
INT1 ModularFactorialInverseLoopMethod( const INT2& n , const INT2& n_min )
{

  INT1 f = 1;

  for( INT2 i = n_min ; i <= n ; i++ ){

    f /= i;

  }

  return f;

}

template <typename INT>
INT Combination( const INT& n , const INT& m , const string& mode )
{

  if( n < m ){

    return 0;

  }

  if( mode == "loop" ){

    return CombinationLoopMethod<INT>( n , m );

  }

  if( mode == "factorial normal" ){

    return CombinationFactorialNormalMethod<INT>( n , m );

  }

  if( mode == "factorial loop" ){

    return CombinationFactorialLoopMethod<INT>( n , m );

  }

  if( mode == "modular factorial inverse normal" ){

    return CombinationModularFactorialInverseNormalMethod<INT>( n , m );

  }

  if( mode == "modular factorial inverse loop" ){

    return CombinationModularFactorialInverseLoopMethod<INT>( n , m );

  }

  return CombinationNormalMethod<INT>( n , m );

}

template <typename INT>
const INT& CombinationNormalMethod( const INT& n , const INT& m )
{

  // const参照返しなので静的const変数を返す。
  if( m == 0 ){

    static const INT one = 1;
    return one;

  }
  
  static VLArray<INT> memory_n{};
  static VLArray<VLArray<INT> > memory_m{};
  static VLArray<VLArray<INT> > memory_answer{};
  VLArray<INT>* p_m = nullptr;
  VLArray<INT>* p_answer = nullptr;

  auto itr_n = memory_n.begin() , end_n = memory_n.end();
  auto itr_m = memory_m.begin();
  auto itr_answer = memory_answer.begin();

  while( itr_n != end_n && p_m == nullptr ){

    if( *itr_n == n ){

      p_m = &( *itr_m );
      p_answer = &( *itr_answer );

    }

    itr_n++;
    itr_m++;
    itr_answer++;

  }

  if( p_m == nullptr ){

    memory_n.push_front( n );
    memory_m.push_front( VLArray<INT>() );
    memory_answer.push_front( VLArray<INT>() );
    p_m = &( memory_m.front() );
    p_answer = &( memory_answer.front() );

  }

  const INT size = p_m->size();

  // p_mには{...,3,2,1}と入っていくのでm <= sizeの時にmが見付かる。
  if( m <= size ){

    auto itr_m_current = p_m->begin() , end_m_current = p_m->end();
    auto itr_answer_current = p_answer->begin();

    while( itr_m_current != end_m_current ){

      if( *itr_m_current == m ){

	return *itr_answer_current;

      }

      itr_m_current++;
      itr_answer_current++;

    }

  }
  
  const INT answer = ( CombinationNormalMethod<INT>( n , m - 1 ) * ( n - m + 1 ) ) / m;
  p_m->push_front( m );
  p_answer->push_front( answer );  
  return p_answer->front();

}

template <typename INT>
INT CombinationLoopMethod( const INT& n , const INT& m )
{

  const INT m_comp = n - m;
  const INT m_copy = m_comp < m ? m_comp : m;
  INT answer = 1;

  for( INT i = 0 ; i < m_copy ; i++ ){

    answer *= ( n - i );
    answer /= i + 1;

  }
  
  return answer;

}

template <typename INT> inline INT CombinationFactorialNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) / Factorial<INT>( m , 1 , "normal" ); }

template <typename INT> inline INT CombinationFactorialLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) / Factorial<INT>( m , 1 , "loop" ); }

template <typename INT> inline INT CombinationModularFactorialInverseNormalMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "normal" ) * ModularFactorialInverse<INT,INT>( m , 1 , "normal" ); }

template <typename INT> inline INT CombinationModularFactorialInverseLoopMethod( const INT& n , const INT& m ) { return Factorial<INT>( n , n - m + 1 , "loop" ) * ModularFactorialInverse<INT,INT>( m , 1 , "loop" ); }



constexpr const ll P = 998244353;

int main(){
  CIN( ll , N );
  CIN( ll , K );
  // S = sum_{i=1}^{N} S(i) e_i = sum_{i=1}^{N} S(i) (e_i - e_1)
  // = sum_{i=1}^{N} S(i) sum_{j=1}^{i-1} b_j
  // = sum_{j=1}^{N} ( ( sum_{i=j+1}^{N} S(i) ) % 2 ) b_j

  // f(S) = sum_{j=1}^{N} ( sum_{i=j+1}^{N} S(i) ) % 2
  // = Sの1のうち右から数えて奇数番目のものの左に続く0の個数+1の総和

  // #{S|f(S) = d} = N個のうち左端以外からd個選ぶ方法の総数 = C( N - 1 , d )
  // answer = sum_{d=0}^{N-1} C(N-1,d) d^K;
  ll N_minus = N - 1;
  const string mode_comb = "normal";
  const string mode_pow = "binary";
  Mod<P> answer{ 0 };  
  FOR_LL( d , 0 , N ){
    answer += Combination<Mod<P> >( N_minus , d , mode_comb ) * Power<Mod<P>,ll>( Mod<P>( d ) , K , 1 , true , mode_pow );
  }
  RETURN( answer.Represent() );
}
yukicoder

結果

テストケース

ソースコード
