結果

問題 No.2068 Restricted Permutation
ユーザー 👑 p-adic
提出日時 2022-09-19 16:34:49
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 29,737 bytes
コンパイル時間 1,990 ms
コンパイル使用メモリ 204,408 KB
最終ジャッジ日時 2025-02-07 12:32:32
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #define _GLIBCXX_DEBUG 
#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 UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( ll VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << "\n"; QUIT 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : - a; }
template <typename T>
using VLArray = list<T>;
// 以下、自分のライブラリ（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;
}
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-() const noexcept;
  // 前置++/--を使うつもりがないので後置++/--と同じものとして定義する
  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 );
template <INT_TYPE_FOR_MOD M> inline string to_string( const Mod<M>& n ) noexcept;
template<INT_TYPE_FOR_MOD M , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const Mod<M>& n );
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-() const noexcept { return Mod<M>( 0 ).operator-=( *this ); }
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; }
template <INT_TYPE_FOR_MOD M> inline string to_string( const Mod<M>& n ) noexcept { return to_string( n.Represent() ) + " + MZ"; }
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;
}
template<INT_TYPE_FOR_MOD M , class Traits> inline basic_ostream<char,Traits>& operator<<( basic_ostream<char,Traits>& os , const Mod<M>& n ) { 
    return os << n.Represent(); }
constexpr const ll P = 998244353;
using MOD = Mod<P>;
int main()
{
  CIN( ll , N );
  if( N == 1 ){
    RETURN( 0 );
  }
  CIN( ll , K );
  CIN( ll , X );
  // 条件を満たす各順列PとN以下の正整数iに対し、
  // 長さNの順列であってPとi-1項目までは一致しi項目が一致せずPより辞書式順序で小さいものの個数をf(P,i)と置けば
  // sum_P f(P) = sum_P sum_i f(P,i) = sum_i sum_P f(P,i)となる。
  // 従って各iに対しsum_P f(P,i)を計算し総和を取ればよい。
  // 各i < Kに対する和
  // = sum_P (P[i]未満かつ第i未満成分と一致しないN以下の正整数の個数) * Factorial( N - i )
  // = Factorial( N - i ) * sum_P (P[i]未満かつ第i未満成分と一致しないN以下の正整数の個数)
  // = Factorial( N - i ) * sum( ll j = 0 ; j <= N - i ) ; j++ )
  //   { j * (条件を満たす順列PのうちP[i]未満かつ第i未満成分と一致しないN以下の正整数の個数がj個であるものの個数) }
  // = Factorial( N - i ) * sum( ll j = 0 ; j <= N - i ) ; j++ )
  //   {
  //     j * sum( ll Pi = j + 1 ; Pi <= i + j ; Pi++ )
  //     {
  //       ( Pi == X ? 0 : Pi未満の正整数をj個選ぶ選び方の個数)
  //       * ( Piより大きいN以下の正整数を(i-1)-((Pi-1)-j)個選ぶ選び方の個数)
  //       * (長さi-1の順列の個数) * (長さN-i-1の順列の個数)
  //     }
  //   }
  // = Factorial( N - i ) * sum( ll j = 0 ; j <= N - i ) ; j++ )
  //   {
  //     j * sum( ll Pi = j + 1 ; Pi <= i + j ; Pi++ )
  //     {
  //       ( Pi == X ? 0 : Pi未満の正整数をj個選ぶ選び方の個数)
  //       * ( Piより大きいN以下の正整数をN-i-j個選ぶ選び方の個数)
  //       * Factrial( i - 1 ) * Factorial( N - i - 1 )
  //     }
  //   }
  // = Factorial( N - i ) * Factrial( i - 1 ) * Factorial( N - i - 1 )
  //   * sum( ll j = 0 ; j <= N - i ) ; j++ )
  //   {
  //     j * (N以下の正整数をN-i+1個選ぶ選び方のうちXを選びかつj+1番目に小さい数がXでないものの個数)
  //   }
  // = Factorial( N - i ) * Factrial( i - 1 ) * Factorial( N - i + 1 )
  //   * sum( ll j = 0 ; j <= N - i ) ; j++ )
  //   {
  //     j *
  //     (
  //       (N-1以下の正整数をN-i個選ぶ選び方の個数)
  //       - (X未満の正整数をj個選ぶ選び方の個数) * (Xより大きいN以下の整数をN-i-j個選ぶ選び方の個数)
  //     )
  //   }
  // = Factorial( N - i ) * Factrial( i - 1 ) * Factorial( N - i - 1 ) *
  //   (
  //     sum( ll j = 0 ; j <= N - i ) ; j++ ){ j * Combination( N - 1 , ( N - i ) }
  //     - (Xでない正整数をN-i個選ぶ各選び方に対するX未満の選ばれた数の個数の総和)
  //   )
  // = Factorial( N - i ) * Factrial( i - 1 ) * Factorial( N - i - 1 ) *
  //   (
  //     Combination( N - 1 , i - 1 ) * sum( ll j = 0 ; j <= N - i ) ; j++ ) j
  //     - Combination( N - 1 , N - i ) * ( ( N - i ) * ( X - 1 ) / ( N - 1 ) )
  //   )
  // = Factorial( N - i ) * Factrial( i - 1 ) * Factorial( N - i - 1 ) *
  //   (
  //     Combination( N - 1 , i - 1 ) * ( ( N - i ) * ( N - i + 1 ) ) / 2
  //     - Combination( N - 1 , N - i ) * ( ( N - i ) * ( X - 1 ) / ( N - 1 ) )
  //   )
  // = Factorial( N - 1 ) * Factorial( N - i ) * ( ( N - i + 1 ) / 2 - ( X - 1 ) / ( N - 1 ) )
  // i = Kに対する和
  // = sum_P (X未満かつ第i未満成分と一致しないN以下の正整数の個数) * Factorial( N - K )
  // = Factorial( N - K ) * sum( ll j = 0 ; j <= N - K ) ; j++ )
  //   {
  //     j * (X未満の正整数をj個選ぶ選び方の個数)
  //     * (Xより大きいN以下の正整数を(K-1)-((X-1)-j)個選ぶ選び方の個数)
  //     * (長さK-1の順列の個数) * (長さN-Kの順列の個数)
  //   }
  // = Factorial( N - K ) * sum( ll j = max( 0 , X - K ) ; j <= min( N - K , X - 1 ) ) ; j++ )
  //   {
  //     j * Combination( X - 1 , j ) * Combination( N - X , K + j - X )
  //     * Factorial( K - 1 ) * Factorial( N - K )
  //   }
  // = Factorial( N - K ) * Factorial( K - 1 ) * Factorial( N - K )
  //   * sum( ll j = max( 0 , X - K ) ; j <= min( N - K , X - 1 ) ) ; j++ )
  //   { j * Combination( X - 1 , j ) * Combination( N - X , N - K - j ) }
  // = Factorial( N - K ) * Factorial( K - 1 ) * Factorial( N - K - 1 )
  //   * (Xでない正整数をN-K個選ぶ各選び方に対するX未満の選ばれた数の個数の総和)
  // = Factorial( N - K ) * Factorial( K - 1 ) * Factorial( N - K )
  //   * Combination( N - 1 , N - K ) * ( ( N - K ) * ( X - 1 ) / ( N - 1 ) )
  // = Factorial( N - 1 ) * Factorial( N - K ) * ( N - K ) * ( X - 1 ) / ( N - 1 )
  
  // i > K全体に対する総和
  // = ( Factorial( N - 1 ) / Factorial( N - 1 - ( K - 1 ) ) ) * sum( ll p = 0 ; p < Factorial( N - K ) ; p++ ) p
  // = ( Factorial( N - 1 ) / Factorial( N - K ) ) * ( Factorial( N - K ) * ( Factorial( N - K ) - 1 ) ) / 2
  // = Factorial( N - 1 ) * ( Factorial( N - K ) - 1 ) / 2
  MOD answer{};
  MOD Factorial[200001];
  MOD one{ 1 };
  Factorial[0] = one;
  FOR( i , 1 , N ){
    Factorial[i] = Factorial[i-1] * i;
  }
  MOD two_inverse = one / 2;
  MOD rate = MOD( X - 1 ) / ( N - 1 );
  ll NK = N - K;
  FOR( N_minus_i , NK + 1 , N ){
    answer += Factorial[N_minus_i] * ( ( N_minus_i + 1 ) * two_inverse - rate );
  }
  answer += Factorial[NK] * NK * rate;
  answer += ( Factorial[NK] -  1 ) * two_inverse;
  answer *= Factorial[N-1];
  RETURN( answer );
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0