#779775 (C++14) No.1815 K色問題

提出ソース
結果

問題	No.1815 K色問題
ユーザー	👑 p-adic
提出日時	2022-07-20 12:17:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	55,329 bytes
コンパイル時間	2,183 ms
コンパイル使用メモリ	125,768 KB
実行使用メモリ	19,540 KB
最終ジャッジ日時	2024-09-29 22:46:08
合計ジャッジ時間	10,081 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	AC	439 ms 19,408 KB
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <chrono>

using namespace std;
using ll = long long;
using INT_TYPE_FOR_MOD = ll;
using INT_TYPE_FOR_ADIC_INT = ll;
template <typename T> using VLArray = list<T>;
#define PRIME_NUMBER 1000000007 
#define MOD Mod<PRIME_NUMBER>

// 自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。

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;

}




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; }


// ここを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" );

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



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 <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 ); }

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" ); }

template <typename T>
using LineTypeForMatrix = vector<T>;

template <typename T>
using TableTypeForMatrix = LineTypeForMatrix<LineTypeForMatrix<T> >;

using SizeTypeForMatrix = ll;

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
class Matrix
{

private:
  TableTypeForMatrix<T>  m_M;

public:
  // argsの長さがXYでなくてもコンパイルエラーとならないがサポート外である。
  template <typename... Args> Matrix( const Args&... args ) noexcept;

  inline Matrix( const Matrix<Y,X,T>& mat ) noexcept;

  // ( X , Y )行列でないものも引数に取れるがサポート外である。
  template <typename... Args> inline Matrix( const TableTypeForMatrix<T>& M ) noexcept;

  Matrix<Y,X,T>& operator=( const Matrix<Y,X,T>& mat ) noexcept;
  Matrix<Y,X,T>& operator+=( const Matrix<Y,X,T>& mat );
  Matrix<Y,X,T>& operator-=( const Matrix<Y,X,T>& mat );
  Matrix<Y,X,T>& operator*=( const T& scalar ) noexcept;

  // 行や列の長さを変更可能だがサポート外である。
  inline TableTypeForMatrix<T>& RefTable() noexcept;
  inline const TableTypeForMatrix<T>& GetTable() const noexcept;

  static inline const Matrix<Y,X,T>& Unit() noexcept;

private:
  static inline void ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec ) noexcept;
  template <typename Arg , typename... Args> static void ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec , const Arg& arg , const Args&... args ) noexcept;
  
  static Matrix<Y,X,T> Unit_Body() noexcept;

};

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator==( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept;

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator!=( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept;

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator+( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator-( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , SizeTypeForMatrix Z , typename T>
Matrix<Y,Z,T> operator*( const Matrix<Y,X,T>& mat1 , const Matrix<X,Z,T>& mat2 );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator*( const T& scalar , const Matrix<Y,X,T>& mat );

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<X,Y,T> Transpose( const Matrix<Y,X,T>& mat );

template <SizeTypeForMatrix X , typename T>
T Trace( const Matrix<X,X,T>& mat );

// ../Arithmetic/Power/a_Body.hppにて定義
// template <typename T , typename UINT>
// T PowerBinaryMethod( const T& t , const UINT& num , const T& init , const bool& for_right_multiplication );
template <typename T , typename UINT>
Matrix<2,2,T> PowerBinaryMethod( const Matrix<2,2,T>& mat , const UINT& num , const Matrix<2,2,T>& init_dummy , const bool& for_right_multiplication_dummy );

template <typename T>
class TwoByTwoMatrix
{

private:
  T m_M00;
  T m_M01;
  T m_M10;
  T m_M11;

public:
  inline TwoByTwoMatrix( const T& M00 , const T& M01 , const T& M10 , const T& M11 ) noexcept;
  TwoByTwoMatrix( const Matrix<2,2,T>& mat );
  TwoByTwoMatrix<T>& operator=( const TwoByTwoMatrix<T>& mat ) noexcept;

  inline Matrix<2,2,T> GetMatrix22() const noexcept;

  static inline TwoByTwoMatrix<T> Multiply( const TwoByTwoMatrix<T>& mat1 , const TwoByTwoMatrix<T>& mat2 );
  static inline TwoByTwoMatrix<T> Square( const TwoByTwoMatrix<T>& mat );
  
};

template <typename T> inline TwoByTwoMatrix<T> operator*( const TwoByTwoMatrix<T>& mat1 , const TwoByTwoMatrix<T>& mat2 );

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


template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename... Args>
Matrix<Y,X,T>::Matrix( const Args&... args ) noexcept
  : m_M()
{

  TableTypeForMatrix<T> M{};
  LineTypeForMatrix<T> vec{};
  ConstructTable( M , vec , args... );
  m_M = M;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T>::Matrix( const Matrix<Y,X,T>& mat ) noexcept : m_M( mat.m_M ) {}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename... Args> inline Matrix<Y,X,T>::Matrix( const TableTypeForMatrix<T>& M ) noexcept : m_M( M ) {}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator=( const Matrix<Y,X,T>& mat ) noexcept
{

  m_M = mat.m_M;
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator+=( const Matrix<Y,X,T>& mat )
{

  auto itr1y = m_M.begin() , end1y = m_M.end();
  auto itr2y = mat.m_M.begin();  

  while( itr1y != end1y ){

    auto itr1xy = itr1y->begin() , end1xy = itr1y->end();
    auto itr2xy = itr2y->begin();  

    while( itr1xy != end1xy ){

      *itr1xy += *itr2xy;
      itr1xy++;
      itr2xy++;

    }
    
    itr1y++;
    itr2y++;

  }
  
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T>& Matrix<Y,X,T>::operator-=( const Matrix<Y,X,T>& mat )
{

  auto itr1y = m_M.begin() , end1y = m_M.end();
  auto itr2y = mat.m_M.begin();  

  while( itr1y != end1y ){

    auto itr1xy = itr1y->begin() , end1xy = itr1y->end();
    auto itr2xy = itr2y->begin();  

    while( itr1xy != end1xy ){

      *itr1xy -= *itr2xy;
      itr1xy++;
      itr2xy++;

    }
    
    itr1y++;
    itr2y++;

  }
  
  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> Matrix<Y,X,T>& Matrix<Y,X,T>::operator*=( const T& scalar ) noexcept
{

  for( auto itry = m_M.begin() , endy = m_M.end() ; itry != endy ; itry++ ){

    for( auto itrxy = itry->begin() , endxy = itry->end() ; itrxy != endxy ; itrxy++ ){

      *itrxy *= scalar;

    }

  }

  return *this;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline TableTypeForMatrix<T>& Matrix<Y,X,T>::RefTable() noexcept { return m_M; }
template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline const TableTypeForMatrix<T>& Matrix<Y,X,T>::GetTable() const noexcept { return m_M; }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline const Matrix<Y,X,T>& Matrix<Y,X,T>::Unit() noexcept { static const Matrix<Y,X,T> unit = Unit_Body(); return unit; }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> Matrix<Y,X,T>::Unit_Body() noexcept
{

  TableTypeForMatrix<T> M{};
  
  for( SizeTypeForMatrix y = 0 ; y < Y ; y++ ){

    LineTypeForMatrix<T> vec{};

    for( SizeTypeForMatrix x = 0 ; x < X ; x++ ){

      vec.push_back( x == y ? 1 : 0 );

    }

    M.push_back( vec );

  }

  return Matrix<Y,X,T>( M );

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline void Matrix<Y,X,T>::ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec ) noexcept { M.push_back( vec ); vec.clear(); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> template <typename Arg , typename... Args> void Matrix<Y,X,T>::ConstructTable( TableTypeForMatrix<T>& M , LineTypeForMatrix<T>& vec , const Arg& arg , const Args&... args ) noexcept
{

  vec.push_back( arg );

  if( vec.size() == X ){

    ConstructTable( M , vec );

  }

  if( M.size() < Y ){

    ConstructTable( M , vec , args... );

  }
  
  return;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator==( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept { return mat1.GetTable() == mat2.GetTable(); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T> inline Matrix<Y,X,T> operator!=( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 ) noexcept { return !( mat1 == mat2 ); }

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator+( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 )
{

  Matrix<Y,X,T> mat1_copy = mat1;
  mat1_copy += mat2;
  return mat1_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator-( const Matrix<Y,X,T>& mat1 , const Matrix<Y,X,T>& mat2 )
{

  Matrix<Y,X,T> mat1_copy = mat1;
  mat1_copy -= mat2;
  return mat1_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , SizeTypeForMatrix Z , typename T> inline Matrix<Y,Z,T> operator*( const Matrix<Y,X,T>& mat1 , const Matrix<X,Z,T>& mat2 )
{

  const TableTypeForMatrix<T>& M1 = mat1.GetTable();
  const TableTypeForMatrix<T>& M2 = mat2.GetTable();
  TableTypeForMatrix<T> M_prod{};
  auto begin2x = M2.begin();
  
  for( auto itr1y = M1.begin() , end1y = M1.end() ; itr1y != end1y ; itr1y++ ){

    LineTypeForMatrix<T> vec{};
    auto begin1yx = itr1y->begin() , end1yx = itr1y->end();

    for( SizeTypeForMatrix z = 0 ; z < Z ; z++ ){

      auto itr1yx = begin1yx;
      auto itr2x = begin2x;

      T inner_product = 0;
      
      while( itr1yx != end1yx ){

	inner_product += ( *itr1yx ) * ( *itr2x )[z];
	itr1yx++;
	itr2x++;

      }

      vec.push_back( inner_product );

    }

    M_prod.push_back( vec );

  }

  return Matrix<Y,Z,T>( M_prod );

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<Y,X,T> operator*( const T& scalar , const Matrix<Y,X,T>& mat )
{

  Matrix<Y,X,T> mat_copy = mat;
  mat_copy *= scalar;
  return mat_copy;

}

template <SizeTypeForMatrix Y , SizeTypeForMatrix X , typename T>
Matrix<X,Y,T> Transpose( const Matrix<Y,X,T>& mat )
{

  const TableTypeForMatrix<T>& M = mat.GetTable();
  TableTypeForMatrix<T> M_t{};

  auto beginy = M.begin();

  for( auto itr1x = beginy->begin() , end1x = beginy->end() ; itr1x != end1x ; itr1x++ ){

    M_t.push_back( LineTypeForMatrix<T>() );

  }

  for( auto itry = beginy , endy = M.end() ; itry != endy ; itry++ ){

    auto itryx = itry->begin() , endyx = itry->end();
    auto itr_ty = M_t.begin();

    while( itryx != endyx ){

      itr_ty->push_back( *itryx );
      itryx++;
      itr_ty++;

    }

  }

  return Matrix<X,Y,T>( M_t );

}

template <SizeTypeForMatrix X , typename T>
T Trace( const Matrix<X,X,T>& mat )
{

  int i = 0;
  T answer =0;
  const TableTypeForMatrix<T>& M = mat.GetTable();

  for( auto itry = M.begin() , endy = M.end() ; itry != endy ; itry++ ){

    answer += ( *itry )[i];
    i++;

  }

  return answer;

}

template <typename T , typename UINT> inline Matrix<2,2,T> PowerBinaryMethod( const Matrix<2,2,T>& mat , const UINT& num , const Matrix<2,2,T>& init_dummy , const bool& for_right_multiplication_dummy ) { return PowerBinaryMethod( TwoByTwoMatrix<T>( mat ) , num , TwoByTwoMatrix<T>( init_dummy ) , for_right_multiplication_dummy ).GetMatrix22(); }

template <typename T> inline TwoByTwoMatrix<T>::TwoByTwoMatrix( const T& M00 , const T& M01 , const T& M10 , const T& M11 ) noexcept : m_M00( M00 ) , m_M01( M01 ) , m_M10( M10 ) , m_M11( M11 ) {}

template <typename T>
TwoByTwoMatrix<T>::TwoByTwoMatrix( const Matrix<2,2,T>& mat )
  : m_M00() , m_M01() , m_M10() , m_M11()
{

  const TableTypeForMatrix<T>& M = mat.GetTable();
  const LineTypeForMatrix<T>& M0 = M[0];
  const LineTypeForMatrix<T>& M1 = M[1];
  m_M00 = M0[0];
  m_M01 = M0[1];
  m_M10 = M1[0];
  m_M11 = M1[1];

}

template <typename T>
TwoByTwoMatrix<T>& TwoByTwoMatrix<T>::operator=( const TwoByTwoMatrix<T>& mat ) noexcept
{

  if( &mat != this ){

    m_M00 = mat.m_M00;
    m_M01 = mat.m_M01;
    m_M10 = mat.m_M10;
    m_M11 = mat.m_M11;

  }

  return *this;

}

template <typename T> inline Matrix<2,2,T> TwoByTwoMatrix<T>::GetMatrix22() const noexcept { return Matrix<2,2,T>( m_M00 , m_M01 , m_M10 , m_M11 ); }

template <typename T> inline TwoByTwoMatrix<T> TwoByTwoMatrix<T>::Multiply( const TwoByTwoMatrix<T>& mat1 , const TwoByTwoMatrix<T>& mat2 ) { return TwoByTwoMatrix<T>( mat1.m_M00 * mat2.m_M00 + mat1.m_M01 * mat2.m_M10 , mat1.m_M00 * mat2.m_M01 + mat1.m_M01 * mat2.m_M11 , mat1.m_M10 * mat2.m_M00 + mat1.m_M11 * mat2.m_M10 , mat1.m_M10 * mat2.m_M01 + mat1.m_M11 * mat2.m_M11 ); }

template <typename T> inline TwoByTwoMatrix<T> TwoByTwoMatrix<T>::Square( const TwoByTwoMatrix<T>& mat ) { return TwoByTwoMatrix<T>( mat.m_M00 * mat.m_M00 + mat.m_M01 * mat.m_M10 , ( mat.m_M00 + mat.m_M11 ) * mat.m_M01 , mat.m_M10 * ( mat.m_M00 + mat.m_M11 ) , mat.m_M10 * mat.m_M01 + mat.m_M11 * mat.m_M11 ); }

template <typename T> inline TwoByTwoMatrix<T> operator*( const TwoByTwoMatrix<T>& mat1 , const TwoByTwoMatrix<T>& mat2 ) { return TwoByTwoMatrix<T>::Multiply( mat1 , mat2 ); }

template <typename T> inline TwoByTwoMatrix<T> Square( const TwoByTwoMatrix<T>& mat ) { return TwoByTwoMatrix<T>::Square( mat ); }


MOD Solution( const MOD& N , const ll& M , const MOD& K );

int main()
{

  ll N;
  ll M;
  ll K;

  N = 3;
  M = 771347935690096439;
  K = 158067;
  // cin >> N;
  // cin >> M;
  // cin >> K;

  if( N * M < K ){

    cout << 0 << endl;

  } else {

    cout << Solution( MOD( N ) , M , MOD( K ) ).Represent() << endl;

  }
  
  return 0;

}

MOD A1( const ll& M , const MOD& K );
MOD A2( const ll& M , const MOD& K );
MOD A3( const ll& M , const MOD& K );

MOD Solution( const MOD& N , const ll& M , const MOD& K )
{

  if( N == 1 ){

   return A1( M , K );

  }

  if( N == 2 ){
    
    return A2( M , K );

  }

  return A3( M , K );
  
}

MOD A1( const ll& M , const MOD& K )
{

  // sum( int k = 0 ; true ; k++ ) C( K , k ) * A1( M , k )
  // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A1( M , k )
  // = K * ( K - 1 ) ^ ( M - 1 )

  // A1( M , K ) = MahlerExpansion( X * ( X - 1 ) ^ ( M - 1 ) , K )
  // = Difference ^ K ( X * ( X - 1 ) ^ ( M - 1 ) )( 0 )
  // = ( sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * ( X * ( X - 1 ) ^ ( M - 1 ) )( X + k ) )( 0 )
  // = sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * ( ( X + k ) * ( X + k - 1 ) ^ ( M - 1 ) )( 0 )
  // = sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k ) * k * ( k - 1 ) ^ ( M - 1 )
  // = ( -1 ) ^ K * sum( k = 0 ; k <= K ; k++ ) ( -1 ) ^ k * C( K , k ) * k * ( k - 1 ) ^ ( M - 1 )
  // = ( -1 ) ^ ( K + 1 ) * sum( k = 0 ; k < K ; k++ ) ( -1 ) ^ k * C( K , k + 1 ) * ( k + 1 ) * k ^ ( M - 1 )
  // = ( -1 ) ^ ( K + 1 ) * K * sum( k = 0 ; k < K ; k++ ) ( -1 ) ^ k * C( K - 1 , k ) * k ^ ( M - 1 )
    
  MOD answer = 0;
  const MOD K_decr = K - 1;
  const ll& K_decr_rep = K_decr.Represent();
  const ll M_decr = ( M - 1 ) % ( PRIME_NUMBER - 1 );
  const string mode_comb = "normal";
  const string mode_pow = "binary";

  for( ll k = 0 ; k <= K_decr_rep ; k++ ){

    const MOD d = Combination<MOD>( K_decr , k , mode_comb ) * Power<MOD,ll>( k , M_decr , 1 , true , mode_pow );

    if( k % 2 == 0 ){

      answer += d;

    } else {

      answer -= d;

    }

  }

  answer *= K;
  
  if( K_decr_rep % 2 == 1 ){

    answer *= -1;

  }

  return answer;

}

MOD A2( const ll& M , const MOD& K )
{

  // sum( int k = 0 ; true ; k++ ) C( K , k ) * A2( M , k )
  // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A2( M , k )
  // = K * ( K - 1 ) * ( 1 * ( K - 1 ) + ( K - 2 ) ^ 2 ) ^ ( M - 1 )
  // = K * ( K - 1 ) * ( K ^ 2 - 3 * K + 3 ) ^ ( M - 1 )

  // A2( M , K )
  // = MahlerExpansion( X * ( X - 1 ) * ( X ^ 2 - 3 * X + 3 ) ^ ( M - 1 ) , K )
  // = Difference ^ K ( X * ( X - 1 ) * ( X ^ 2 - 3 * X + 3 ) ^ ( M - 1 ) )( 0 )
  // = sum( int k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) *
  //   C( K , k ) * k * ( k - 1 ) * ( k ^ 2 - 3 * k + 3 ) ^ ( M - 1 )
  // = ( -1 ) ^ K * K * ( K - 1 ) * sum( int k = 2 ; k <= K ; k++ )
  //   ( -1 ) ^ k * C( K - 2 , k - 2 ) * ( k ^ 2 - 3 * k + 3 ) ^ ( M - 1 )
  // = ( -1 ) ^ K * K * ( K - 1 ) * sum( int k = 0 ; k <= K - 2 ; k++ )
  //   ( -1 ) ^ k * C( K - 2 , k ) * ( k ^ 2 + k + 1 ) ^ ( M - 1 )

  MOD answer = 0;
  const MOD K_decr2 = K - 2;
  const ll& K_decr2_rep = K_decr2.Represent();
  const ll M_decr = ( M - 1 ) % ( PRIME_NUMBER - 1 );
  const string mode_comb = "normal";
  const string mode_pow = "binary";

  for( ll k = 0 ; k <= K_decr2_rep ; k++ ){

    const MOD k_copy = k;
    const MOD d = Combination<MOD>( K_decr2 , k_copy , mode_comb ) * Power<MOD,ll>( k_copy * k_copy + k_copy + 1 , M_decr , 1 , true , mode_pow );

    if( k % 2 == 0 ){

      answer += d;

    } else {

      answer -= d;

    }

  }

  answer *= K * ( K - 1 );
  
  if( K_decr2_rep % 2 == 1 ){

    answer *= -1;

  }

  return answer;

}

MOD A3( const ll& M , const MOD& K )
{

  // XYX -> X'Y'X'パターン
  // 1 * ( K - 1 ) + ( K - 2 ) ^ 2
  // = K ^ 2 - 3 * K + 3

  // XYX -> X'Y'Z'パターン
  // 1 * ( 1 * ( K - 2 ) + ( K - 2 ) * ( K - 3 ) ) + ( K - 2 ) * ( 1 * ( K - 2 ) + ( K - 3 ) ^ 2 )
  // = ( K - 2 ) ^ 2 + ( K - 2 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 )
  // = ( K - 2 ) * ( K ^ 2 - 4 * K + 5 )
  // = K ^ 3 - 6 * K ^ 2 + 13 * K - 10

  // XYXパターン合計
  // ( K ^ 2 - 3 * K + 3 ) + ( K ^ 3 - 6 * K ^ 2 + 13 * K - 10 )
  // = K ^ 3 - 5 * K ^ 2 + 10 * K - 7

  // XYZ -> X'Y'X'パターン
  // 1 * ( K - 1 ) + ( K - 3 ) * ( K - 2 )
  // = K ^ 2 - 4 * K + 5

  // XYZ -> X'Y'Z'パターン
  // 1 * ( 1 * ( K - 2 ) + ( K - 2 ) * ( K - 3 ) ) + 1 * ( K - 2 ) ^ 2 + ( K - 3 ) * ( 1 * ( K - 2 ) + ( K - 3 ) ^ 2 )
  // = ( K - 2 ) ^ 2 + ( K - 2 ) ^ 2 + ( K - 3 ) * ( ( K - 2 ) + ( K - 3 ) ^ 2 )
  // = 2 * ( K - 2 ) ^ 2 + ( K - 3 ) * ( K ^ 2 - 5 * K + 7 )
  // = 2 * ( K - 2 ) ^ 2 + K ^ 3 - 8 * K ^ 2 + 22 * K - 21
  // = K ^ 3 - 6 * K ^ 2 + 14 * K - 13

  // XYZパターン合計
  // ( K ^ 2 - 4 * K + 5 ) + ( K ^ 3 - 6 * K ^ 2 + 14 * K - 13 )
  // = K ^ 3 - 5 * K ^ 2 + 10 * K - 8

  // Transfer( X )
  // = Matrix<2,2>(
  //   X ^ 2 - 3 * X + 3 , X ^ 2 - 4 * X + 5 ,
  //   X ^ 3 - 6 * X ^ 2 + 13 * X - 10 , X ^ 3 - 6 * X ^ 2 + 14 * X - 13
  //   )

  // Transfer( X + 2 )
  // = Matrix<2,2>(
  //   X ^ 2 + X + 1 , X ^ 2 + 1 ,
  //   X ^ 3 + X , X ^ 3 + 2 * X - 1
  //   )

  // tr( Transfer( X + 2 ) )
  // = ( X ^ 2 + X + 1 ) + ( X ^ 3 + 2 * X - 1 )
  // = X ^ 3 + X ^ 2 + 3 * X

  // det( Transfer( X + 2 ) )
  // = ( X ^ 2 + X + 1 ) * ( X ^ 3 + 2 * X - 1 )
  //   - ( X ^ 2 + 1 ) * ( X ^ 3 + X )
  // = X ^ 5 + X ^ 4 + 3 * X ^ 3 + X ^ 2 + X - 1
  //   - X ^ 5 - 2 * X ^ 3 - X
  // = X ^ 4 + X ^ 3 + X ^ 2 - 1
  // = ( X + 1 ) * ( X ^ 3 + X - 1 )

  // -> Transfer( X + 2 )はMOD[X]で対角化不可能
  
  // sum( int k = 0 ; true ; k++ ) C( K , k ) * A3( M , k )
  // = sum( int k = 0 ; k <= K ; k++ ) C( K , k ) * A3( M , k )
  // = tr(
  //     Matrix<1,2>( 1 , 1 ) * Transfer( K ) ^ ( M - 1 )
  //      * Matrix<2,1>( K * ( K - 1 ) , K * ( K - 1 ) * ( K - 2 ) )
  //     )

  // A3( M , K )
  // = MahlerExpansion(
  //     Trace(
  //       Matrix<1,2>( 1 , 1 ) * Transfer( X ) ^ ( M - 1 )
  //        * Matrix<2,1>( X * ( X - 1 ) , X * ( X - 1 ) * ( X - 2 ) )
  //       ) ,
  //     K
  //   )
  // = Difference ^ K (
  //     Trace(
  //       Matrix<1,2>( 1 , 1 ) * Transfer( X ) ^ ( M - 1 )
  //        * Matrix<2,1>( X * ( X - 1 ) , X * ( X - 1 ) * ( X - 2 ) )
  //     )
  //   )( 0 )
  // = sum( int k = 0 ; k <= K ; k++ ) ( -1 ) ^ ( K - k ) * C( K , k )
  //   * tr(
  //     Matrix<1,2>( 1 , 1 ) * Transfer( k ) ^ ( M - 1 )
  //      * Matrix<2,1>( k * ( k - 1 ) , k * ( k - 1 ) * ( k - 2 ) )
  //   )
  // = ( -1 ) ^ K * K * ( K - 1 ) * tr( Matrix<1,2>( 1 , 1 )
  //     * sum( int k = 2 ; k <= K ; k++ ) ( -1 ) ^ k * C( K - 2 , k - 2 ) * Transfer( k ) ^ ( M - 1 ) * Matrix<2,1>( 1 , k - 2 )
  //    )
  // = ( -1 ) ^ K * K * ( K - 1 ) * tr( Matrix<1,2>( 1 , 1 )
  //     * sum( int k = 0 ; k <= K - 2 ; k++ ) ( -1 ) ^ k * C( K - 2 , k ) * Transfer( k + 2 ) ^ ( M - 1 ) * Matrix<2,1>( 1 , k )
  //    )

  Matrix<2,1,MOD> answer_vec{ 0 , 0 };

  const MOD one = 1;
  const MOD K_decr2 = K - 2;
  const ll& K_decr2_rep = K_decr2.Represent();
  const ll M_decr = M - 1;
  const string mode_comb = "normal";
  const string mode_pow = "binary";

  for( ll k = 0 ; k <= K_decr2_rep ; k++ ){

    const MOD k_copy = k;
    const MOD k_copy2 = k_copy * k;
    const MOD k_copy3 = k_copy2 * k;
    Matrix<2,2,MOD> Transfer{
      k_copy2 + ( k + 1 ) , k_copy2 + 1 ,
  	k_copy3 + k , k_copy3 + ( 2 * k - 1 )
  	};
    const MOD d1 = Combination<MOD>( K_decr2 , k_copy , mode_comb );
    const Matrix<2,2,MOD> d2 = Power<Matrix<2,2,MOD>,ll>( Transfer , M_decr , Matrix<2,2,MOD>::Unit() , true , mode_pow );
    const Matrix<2,1,MOD> d3{ one , k_copy };
    const Matrix<2,1,MOD> d = d1 * d2 * d3;

    if( k % 2 == 0 ){

      answer_vec += d;

    } else {

      answer_vec -= d;

    }

  }

  MOD answer = Trace<1,MOD>( Matrix<1,2,MOD>( one , one ) * answer_vec );
    
  if( K_decr2_rep % 2 == 1 ){

    answer *= -1;

  }

  answer *= K * ( K - 1 );
  return answer;

}
yukicoder

結果

テストケース

ソースコード
