結果

問題 No.2075 GCD Subsequence
ユーザー 👑 p-adicp-adic
提出日時 2023-06-11 10:53:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,676 ms / 4,000 ms
コード長 54,532 bytes
コンパイル時間 5,010 ms
コンパイル使用メモリ 329,212 KB
実行使用メモリ 11,472 KB
最終ジャッジ日時 2023-08-31 01:53:56
合計ジャッジ時間 50,369 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
11,256 KB
testcase_01 AC 6 ms
11,196 KB
testcase_02 AC 7 ms
11,124 KB
testcase_03 AC 6 ms
11,208 KB
testcase_04 AC 7 ms
11,464 KB
testcase_05 AC 6 ms
11,360 KB
testcase_06 AC 6 ms
11,216 KB
testcase_07 AC 6 ms
11,220 KB
testcase_08 AC 398 ms
11,128 KB
testcase_09 AC 632 ms
11,232 KB
testcase_10 AC 420 ms
11,128 KB
testcase_11 AC 538 ms
11,232 KB
testcase_12 AC 471 ms
11,272 KB
testcase_13 AC 349 ms
11,404 KB
testcase_14 AC 532 ms
11,220 KB
testcase_15 AC 371 ms
11,472 KB
testcase_16 AC 396 ms
11,204 KB
testcase_17 AC 628 ms
11,120 KB
testcase_18 AC 3,523 ms
11,128 KB
testcase_19 AC 3,509 ms
11,208 KB
testcase_20 AC 3,517 ms
11,428 KB
testcase_21 AC 3,559 ms
11,208 KB
testcase_22 AC 3,518 ms
11,300 KB
testcase_23 AC 3,520 ms
11,124 KB
testcase_24 AC 3,520 ms
11,300 KB
testcase_25 AC 3,514 ms
11,264 KB
testcase_26 AC 3,521 ms
11,204 KB
testcase_27 AC 3,521 ms
11,360 KB
testcase_28 AC 3,676 ms
11,416 KB
testcase_29 AC 6 ms
11,212 KB
testcase_30 AC 7 ms
11,464 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef DEBUG
  #define _GLIBCXX_DEBUG
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , DEBUG_VALUE )
  #define CERR( ANSWER ) cerr << ANSWER << endl;
  #define LIBRARY_SEARCH if( LibrarySearch() != 0 ){ QUIT; };
#else
  #pragma GCC optimize ( "O3" )
  #pragma GCC optimize( "unroll-loops" )
  #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
  #define DEXPR( LL , BOUND , VALUE , DEBUG_VALUE ) CEXPR( LL , BOUND , VALUE )
  #define CERR( ANSWER ) 
  #define LIBRARY_SEARCH
#endif
#include <bits/stdc++.h>
using namespace std;

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

#define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) )
#define TYPE_OF( VAR ) decay_t<decltype( VAR )>
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define SET_ASSERT( A , MIN , MAX ) cin >> A; ASSERT( A , MIN , MAX )
#define GETLINE( A ) string A; getline( cin , A )
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ )
#define FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT
#define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION )
#define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT

// 圧縮用
#define TE template
#define TY typename
#define US using
#define ST static
#define IN inline
#define CL class
#define PU public
#define OP operator
#define CE constexpr
#define CO const
#define NE noexcept
#define RE return 
#define WH while
#define VO void
#define VE vector
#define LI list
#define BE begin
#define EN end
#define SZ size
#define MO move
#define TH this
#define CRI CO int&
#define CRUI CO uint&
#define CRL CO ll&

#define DEFINITION_OF_GET_FOR_ZETA_TRANSFORM( MU )			\
  list<T> sub = Sub( t );						\
  sub.push_front( t );							\
  U answer = Zero();							\
									\
  while( ! sub.empty() ){						\
									\
    const T& t_sub = sub.front();					\
    answer = Sum( answer , Prod( m_val[e_inv( t_sub )] , MU( t_sub , t ) ) ); \
    sub.pop_front();							\
									\
  }									\
									\
  return answer;							\

#define DEFINITION_OF_INVERSE_IMAGE_SUM_FOR_ZETA_TRANSFORM( MU )	\
  const T t = f_inv_max( s );						\
  list<S> sub = r( s );							\
  U answer = Zero();							\
									\
  while( ! sub.empty() ){						\
									\
    const T& t_sub = f_inv_max( sub.front() );				\
    answer = Sum( answer , Prod( m_val[e_inv( t_sub )] , MU( t_sub , t ) ) ); \
    sub.pop_front();							\
									\
  }									\
									\
  return answer;							\

template <typename T , typename U , int size_max>
class ZetaTransformBody
{

private:
  int m_length;
  map<T,int> m_memory;
  vector<T> m_memory_inv;

protected:
  int m_size;
  U m_val[size_max];

public:
  // 仮想継承用にダミーのデフォルトコンストラクタを設定。
  inline ZetaTransformBody( const int& size = 0 );

  inline void Add( const T& t , const U& u );
  inline void AddAll( const U& u );
  inline ZetaTransformBody<T,U,size_max>& operator+=( const ZetaTransformBody<T,U,size_max>& a );
  inline void MultiplyAll( const U& u );
  inline ZetaTransformBody<T,U,size_max>& operator*=( const ZetaTransformBody<T,U,size_max>& a );

  // 子クラスの半順序のメビウス関数のデフォルトの再帰式を使うため、
  // 再帰深度が浅い場合にしか使えない。
  inline U Get( const T& t );
  // muは子クラスの半順序のメビウス関数。
  template <int mu(const T&,const T&)> inline U Get( const T& t );
  inline const U& InitialSegmentSum( const T& t );

  // f_inv_maxは定義域にr(s)を含む部分写像T->Sであり、要件
  // (1) Sは半順序集合である。
  // (2) r(s)は重複を持たない。（よって集合とみなす）
  // (3) sはr(s)の最大元である。
  // (4) 像f_inv_max(s)の要素を上界に持つTの要素全体Rへのfの制限f_Rは順序保存写像R->r(s)である。
  // (5) r(s)の任意の要素tに対しf_inv_max(t)が逆像f_R^{-1}(t)の最大元である。
  // を満たすfが存在する場合にのみ以下の２つをサポート。

  // f( t ) = sを満たすRの要素t全体を渡る総和取得。
  template <typename S , T f_inv_max(const S&) , list<S> r(const S&)> inline U InverseImageSum( const S& s );
  template <typename S , T f_inv_max(const S&) , list<S> r(const S&) , int mu(const T&,const T&)> inline U InverseImageSum( const S& s );
  // f( t ) <= sを満たすRの要素t全体を渡る総和取得。（結果的にrは使わないが要件上はrの存在が必要） 
  template <typename S , T f_inv_max(const S&)> inline const U& IntervalInverseImageSum( const S& s );

  virtual T e( const int& i );
  virtual int e_inv( const T& t );

private:
  virtual const U& Zero() const = 0;
  virtual U Sum( const U& u0 , const U& u1 ) const = 0;
  virtual U Prod( const U& u0 , const U& u1 ) const = 0;
  virtual list<T> Sub( const T& t ) const = 0;
  virtual list<T> Sup( const T& t ) const = 0;
  virtual int Moevius( const T& t0 , const T& t1 ) = 0;

};

template <typename T , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max>
class SemiRingForZetaTransform :
  virtual public ZetaTransformBody<T,U,size_max>
{

public:
  inline SemiRingForZetaTransform( const int& dummy );
  
private:
  inline const U& Zero() const;
  inline U Sum( const U& u0 , const U& u1 ) const;
  inline U Prod( const U& u0 , const U& u1 ) const;

};

template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , int size_max>
class PartiallyOrderedSetForZetaTransform :
  virtual public ZetaTransformBody<T,U,size_max>
{

private:
  map<int,map<int,int> > m_moevius;

  inline list<T> Sub( const T& t ) const;
  inline list<T> Sup( const T& t ) const;
  // デフォルトの再帰式であるため、再帰深度が浅い場合にしか使えない。
  inline int Moevius( const T& t0 , const T& t1 );
  
};

template <typename U , int size_max>
class EnumerationForZetaTransform :
  virtual public ZetaTransformBody<int,U,size_max>
{

private:
  inline int e( const int& i );
  inline int e_inv( const int& t );
  
};

// 入力の範囲内で要件
// (1) Eがint上の半順序<のグラフでE_invが(int,>)のグラフである。
// を満たす場合にのみ以下をサポート。

// 0による初期化O(size_max)
// ゼータ変換前の配列による初期化O(始切片のサイズの総和)

// 一点加算O(終切片[t,∞)のサイズ)
// 全体加算O(size)
// 各点加法O(size)
// 全体乗算O(size)
// (int,<)がjoin半束である場合の畳み込み乗法O(size)

// 一点取得O(始切片(-∞,t]のサイズ×メビウス関数の計算量)
// 区間和取得O(1)

// 逆像和取得O(始切片(-∞,f_inv_max(r_max)]のサイズ×メビウス関数の計算量)
// 区間逆像和取得O(1)
template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max>
class ZetaTransform :
  public PartiallyOrderedSetForZetaTransform<int,E,E_inv,ll,size_max> ,
  public EnumerationForZetaTransform<ll,size_max>
{

public:
  inline ZetaTransform( const int& size );
  inline ZetaTransform( const int& size , const ll ( &a )[size_max] );

private:
  inline const ll& Zero() const;
  inline ll Sum( const ll& u0 , const ll& u1 ) const;
  inline ll Prod( const ll& u0 , const ll& u1 ) const;

};

// 入力の範囲内で要件
// (1) 2^digit <= size_max
// (2) (U,a_U:U^2->U,z_U:1->U,m_U:U^2->U)が単位的環である。
// を満たす場合にのみ以下をサポート。

// z_U()による初期化O(size_max)
// ゼータ変換前の配列による初期化O(digit 2^digit)（可換加法モノイド性を使う）

// 一点加算O(2^digit)（可換加法モノイド性を使う）
// 全体加算O(2^digit)（可換加法モノイド性だけでも実装できるが単位的半環性を使う）
// 各点加法O(2^digit)（加法モノイド性を使う）
// 全体乗算O(2^digit)（半環性を使う）
// 畳み込み乗法O(2^digit)（半環性を使う）

// 一点取得O(2^digit)（単位的環性を使う。愚直と同じオーダー）
// 多点取得O(digit 2^digit)（単位的環性を使う）
// 区間和取得O(1)（可換加法モノイド性を使う）
// 逆像和取得O(始切片(-∞,f_inv_max(r_max)]のサイズ)（単位的環性を使う）
// 区間逆像和取得O(1)（可換加法モノイド性を使う）
template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max>
class FastZetaTransform :
  public SemiRingForZetaTransform<int,U,a_U,z_U,m_U,size_max> ,
  public EnumerationForZetaTransform<U,size_max>
{

private:
  int m_digit;

public:
  inline FastZetaTransform( const int& digit );
  inline FastZetaTransform( const int& digit , const U ( &a )[size_max] );

  inline FastZetaTransform<U,a_U,z_U,m_U,size_max>& operator+=( const FastZetaTransform<U,a_U,z_U,m_U,size_max>& a );
  inline FastZetaTransform<U,a_U,z_U,m_U,size_max>& operator*=( const FastZetaTransform<U,a_U,z_U,m_U,size_max>& a );

  inline void FastMoeviusTransform( U ( &a )[size_max] );

private:
  inline list<int> Sub( const int& t ) const;
  inline list<int> Sup( const int& t ) const;
  inline int Moevius( const int& t0 , const int& t1 );

};

// 入力の範囲内で要件
// (1) EがT上の半順序<のグラフでE_invが(T,>)のグラフである。
// (2) (U,a_U:U^2->U,z_U:1->U,m_U:U^2->U)が単位的環である。
// を満たす場合にのみ以下をサポート。

// z_U()による初期化O(size_max)

// 一点加算O(終切片[t,∞)のサイズ×log_2(size))（可換加法モノイド性を使う）
// 全体加算O(size)（可換加法モノイド性だけでも実装できるが単位的半環性を使う）
// 各点加法O(size)（加法モノイド性を使う）
// 全体乗算O(size)（半環性を使う）
// (T,<)がjoin半束である場合の畳み込み乗法O(size)（半環性を使う）

// 一点取得O(始切片(-∞,t]のサイズ×メビウス関数の計算量×log_2(size))（単位的環性を使う）
// 区間和取得O(log_2(size))（可換加法モノイド性を使う）

// 逆像和取得O(始切片(-∞,f_inv_max(r_max)]のサイズ×メビウス関数の計算量×log_2(size))（単位的環性を使う）
// 区間逆像和取得O(log_2(size))（可換加法モノイド性を使う）
template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max>
class MemorisationZetaTransform :
  public SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max> ,
  public PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>
{

public:
  inline MemorisationZetaTransform( const int& size );
  
};

// 入力の範囲内で要件
// (1) EがT上の半順序<のグラフでE_invが(T,>)のグラフである。
// (2) (U,a_U:U^2->U,z_U:1->U,m_U:U^2->U)が単位的環である。
// (3) enum_T:int->Tとenum_T_inv:int->Tが互いに逆写像である。
// を満たす場合にのみ以下をサポート。

// z_U()による初期化O(size_max)

// 一点加算O(終切片[t,∞)のサイズ)（可換加法モノイド性を使う）
// 全体加算O(size)（可換加法モノイド性だけでも実装できるが単位的半環性を使う）
// 各点加法O(size)（加法モノイド性を使う）
// 全体乗算O(size)（半環性を使う）
// (T,<)がjoin半束である場合の畳み込み乗法O(size)（半環性を使う）

// 一点取得O(始切片(-∞,t]のサイズ×メビウス関数の計算量)（単位的環性を使う）
// 区間和取得O(1)（可換加法モノイド性を使う）

// 逆像和取得O(始切片(-∞,f_inv_max(r_max)]のサイズ×メビウス関数の計算量)（単位的環性を使う）
// 区間逆像和取得O(1)（可換加法モノイド性を使う）
template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)>
class EnumerationZetaTransform :
  public SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max> ,
  public PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>
{

public:
  inline EnumerationZetaTransform( const int& size );

private:
  inline T e( const int& i );
  inline int e_inv( const T& t );

};

template <typename T , typename U , int size_max> inline ZetaTransformBody<T,U,size_max>::ZetaTransformBody( const int& size ) : m_length() , m_memory() , m_memory_inv() , m_size( size ) , m_val() {}
template <typename T , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>::SemiRingForZetaTransform( const int& dummy ) :
  ZetaTransformBody<T,U,size_max>( dummy )
{

  using base = ZetaTransformBody<T,U,size_max>;
  const U& zero = z_U();

  if( base::m_val[0] != zero ){

    for( int i = 0 ; i < base::m_size ; i++ ){

      base::m_val[i] = zero;

    }

  }

}

template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max> inline ZetaTransform<E,E_inv,size_max>::ZetaTransform( const int& size ) :
  ZetaTransformBody<int,ll,size_max>( size ) ,
  PartiallyOrderedSetForZetaTransform<int,E,E_inv,ll,size_max>()
{}

template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max> inline ZetaTransform<E,E_inv,size_max>::ZetaTransform( const int& size , const ll ( &a )[size_max] ) :
  ZetaTransformBody<int,ll,size_max>( size ) ,
  PartiallyOrderedSetForZetaTransform<int,E,E_inv,ll,size_max>() ,
  EnumerationForZetaTransform<ll,size_max>()
{

  using base = ZetaTransformBody<int,ll,size_max>;
  
  for( int i = 0 ; i < base::m_size ; i++ ){

    ll& m_val_i = base::m_val[i];
    list<int> sub_i = E( i );

    while( ! sub_i.empty() ){

      m_val_i += a[sub_i.front()];
      sub_i.pop_front();

    }

  }

}

template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline FastZetaTransform<U,a_U,z_U,m_U,size_max>::FastZetaTransform( const int& digit ) :
  ZetaTransformBody<int,U,size_max>( size ) ,
  SemiRingForZetaTransform<int,U,a_U,z_U,m_U,size_max>( size ) ,
  EnumerationForZetaTransform<U,size_max>()
{}

template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline FastZetaTransform<U,a_U,z_U,m_U,size_max>::FastZetaTransform( const int& digit , const U ( &a )[size_max] ) :
  ZetaTransformBody<int,U,size_max>( 1 << digit ) ,
  SemiRingForZetaTransform<int,U,a_U,z_U,m_U,size_max>( size ) ,
  m_digit( digit )
{

  using base = ZetaTransformBody<int,U,size_max>;
  
  for( int i = 0 ; i < base::m_size ; i++ ){

    base::m_val[i] = a[i];

  }

  int power = 1;

  for( int d = 0 ; d < m_digit ; d++ , power <<= 1 ){

    for( int i = 0 ; i < base::m_size ; i++ ){

      if( ( i & power ) != 0 ){

	U& m_val_i = base::m_val[i];
	m_val_i = a_U( m_val_i , base::m_val[i ^ power] );

      }
      
    }

  }
  
}

template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline MemorisationZetaTransform<T,E,E_inv,U,a_U,z_U,m_U,size_max>::MemorisationZetaTransform( const int& size ) :
  ZetaTransformBody<T,U,size_max>( size ) ,
  SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>( size ) ,
  PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>()
{}

template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline EnumerationZetaTransform<T,E,E_inv,U,a_U,z_U,m_U,size_max,enum_T,enum_T_inv>::EnumerationZetaTransform( const int& size ) :
  ZetaTransformBody<T,U,size_max>( size ) ,
  SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>( size ) ,
  PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>()
{}

template <typename T , typename U , int size_max> inline void ZetaTransformBody<T,U,size_max>::Add( const T& t , const U& u )
{

  list<T> sup = Sup( t );
  sup.push_front( t );

  while( ! sup.empty() ){

    U& m_val_i = m_val[e_inv( sup.front() )];
    m_val_i = Sum( m_val_i , u );
    sup.pop_front();

  }

  return;

}

template <typename T , typename U , int size_max> inline void ZetaTransformBody<T,U,size_max>::AddAll( const U& u )
{

  for( int i = 0 ; i < m_size ; i++ ){

    U& m_val_i = m_val[i];
    m_val_i = Sum( m_val_i , Prod( Sub( e( i ) ).size() , u ) );

  }
  
  return;

}

template <typename T , typename U , int size_max> inline ZetaTransformBody<T,U,size_max>& ZetaTransformBody<T,U,size_max>::operator+=( const ZetaTransformBody<T,U,size_max>& a )
{

  for( int i = 0 ; i < m_size ; i++ ){

    U& m_val_i = m_val[i];
    m_val_i = Sum( m_val_i , a.m_val[i] );

  }
  
  return *this;

}

template <typename T , typename U , int size_max> inline void ZetaTransformBody<T,U,size_max>::MultiplyAll( const U& u )
{

  for( int i = 0 ; i < m_size ; i++ ){

    U& m_val_i = m_val[i];
    m_val_i = Prod( m_val_i , u );
    
  }
  
  return;

}

template <typename T , typename U , int size_max> inline ZetaTransformBody<T,U,size_max>& ZetaTransformBody<T,U,size_max>::operator*=( const ZetaTransformBody<T,U,size_max>& a )
{

  for( int i = 0 ; i < m_size ; i++ ){

    U& m_val_i = m_val[i];
    m_val_i = Prod( m_val_i , a.m_val[i] );

  }
  
  return *this;

}

template <typename T , typename U , int size_max> inline U ZetaTransformBody<T,U,size_max>::Get( const T& t ) { DEFINITION_OF_GET_FOR_ZETA_TRANSFORM( Moevius ); }
template <typename T , typename U , int size_max> template <int mu(const T&,const T&)> inline U ZetaTransformBody<T,U,size_max>::Get( const T& t ) { DEFINITION_OF_GET_FOR_ZETA_TRANSFORM( mu ); }

template <typename T , typename U , int size_max> inline const U& ZetaTransformBody<T,U,size_max>::InitialSegmentSum( const T& t ) { return m_val[e_inv( t )]; }

template <typename T , typename U , int size_max> template <typename S , T f_inv_max(const S&) , list<S> r(const S&)> inline U ZetaTransformBody<T,U,size_max>::InverseImageSum( const S& s ) { DEFINITION_OF_INVERSE_IMAGE_SUM_FOR_ZETA_TRANSFORM( Moevius ); }
template <typename T , typename U , int size_max> template <typename S , T f_inv_max(const S&) , list<S> r(const S&) , int mu(const T&,const T&)> inline U ZetaTransformBody<T,U,size_max>::InverseImageSum( const S& s ) { DEFINITION_OF_INVERSE_IMAGE_SUM_FOR_ZETA_TRANSFORM( mu ); }

template <typename T , typename U , int size_max> template <typename S , T f_inv_max(const S&)> inline const U& ZetaTransformBody<T,U,size_max>::IntervalInverseImageSum( const S& s ) { return m_val[e_inv( f_inv_max( s ) )]; }


template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline void FastZetaTransform<U,a_U,z_U,m_U,size_max>::FastMoeviusTransform( U ( &a )[size_max] )
{

  using base = ZetaTransformBody<int,U,size_max>;
  
  for( int i = 0 ; i < base::m_size ; i++ ){

    a[i] = base::m_val[i];

  }

  int power = 1;

  for( int d = 0 ; d < m_digit ; d++ , power <<= 1 ){

    for( int i = 0 ; i < base::m_size ; i++ ){

      if( ( i & power ) != 0 ){

	U& a_i = a[i];
	a_i = a_U( a_i , m_U( -1 , a[i ^ power] ) );

      }
      
    }

  }

}


template <typename T , typename U , int size_max>
T ZetaTransformBody<T,U,size_max>::e( const int& i )
{
  
  assert( i < m_length );
  return m_memory_inv[i];

}

template <typename U , int size_max> inline int EnumerationForZetaTransform<U,size_max>::e( const int& i ) { return i; }
template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline T EnumerationZetaTransform<T,E,E_inv,U,a_U,z_U,m_U,size_max,enum_T,enum_T_inv>::e( const int& i ) { return enum_T( i ); }

template <typename T , typename U , int size_max>
int ZetaTransformBody<T,U,size_max>::e_inv( const T& t )
{

  if( m_memory.count( t ) == 0 ){

    assert( m_length < m_size );
    m_memory_inv.push_back( t );
    return m_memory[t] = m_length++;

  }
  
  return m_memory[t];

}

template <typename U , int size_max> inline int EnumerationForZetaTransform<U,size_max>::e_inv( const int& t ) { return t; }
template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max , T enum_T(const int&) , int enum_T_inv(const T&)> inline int EnumerationZetaTransform<T,E,E_inv,U,a_U,z_U,m_U,size_max,enum_T,enum_T_inv>::e_inv( const T& t ) { return enum_T_inv( t ); }


template <typename T , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline const U& SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>::Zero() const { return z_U(); }
template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max> inline const ll& ZetaTransform<E,E_inv,size_max>::Zero() const { static const ll zero = 0; return zero; }

template <typename T , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline U SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>::Sum( const U& u0 , const U& u1 ) const { return a_U( u0 , u1 ); }
template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max> inline ll ZetaTransform<E,E_inv,size_max>::Sum( const ll& u0 , const ll& u1 ) const { return u0 + u1; }

template <typename T , typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline U SemiRingForZetaTransform<T,U,a_U,z_U,m_U,size_max>::Prod( const U& u0 , const U& u1 ) const { return m_U( u0 , u1 ); }
template <list<int> E(const int&) , list<int> E_inv(const int&) , int size_max> inline ll ZetaTransform<E,E_inv,size_max>::Prod( const ll& u0 , const ll& u1 ) const { return u0 * u1; }


template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , int size_max> inline list<T> PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>::Sub( const T& t ) const { return E( t ); }
template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline list<int> FastZetaTransform<U,a_U,z_U,m_U,size_max>::Sub( const int& t ) const
{

  list<int> sub{};
  sub.push_back( t );
  int sub_size = 1;
  int power = 1;
  
  for( int d = 0 ; d < m_digit ; d++ , power <<= 1 ){

    if( ( t & power ) != 0 ){

      auto itr = sub.begin();

      for( int i = 0 ; i < sub_size ; i++ , itr++ ){

	sub.push_back( *itr ^ power );

      }

      sub_size <<= 1;

    }

  }
  
  return sub;

}


template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , int size_max> inline list<T> PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>::Sup( const T& t ) const { return E_inv( t ); }

template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> inline list<int> FastZetaTransform<U,a_U,z_U,m_U,size_max>::Sup( const int& t ) const
{

  list<int> sup{};
  sup.push_back( t );
  int sup_size = 1;
  int power = 1;
  
  for( int d = 0 ; d < m_digit ; d++ , power <<= 1 ){

    if( ( t & power ) == 0 ){

      auto itr = sup.begin();

      for( int i = 0 ; i < sup_size ; i++ , itr++ ){

	sup.push_back( *itr | power );

      }

      sup_size <<= 1;

    }

  }
  
  return sup;

}


template <typename T , list<T> E(const T&) , list<T> E_inv(const T&) , typename U , int size_max> inline int PartiallyOrderedSetForZetaTransform<T,E,E_inv,U,size_max>::Moevius( const T& t0 , const T& t1 )
{

  using base = ZetaTransformBody<T,U,size_max>;
  const int i = base::e_inv( t0 );
  const int j = base::e_inv( t1 );
  map<int,int>& moevius_t0 = m_moevius[i];
  bool found = moevius_t0.count( j ) == 1;
  int& answer = moevius_t0[j];

  if( ! found ){

    if( i == j ){

      answer = 1;

    } else {

      list<T> sub = E( t1 );

      while( ! sub.empty() ){

	answer -= Moevius( t0 , sub.front() );
	sub.pop_front();

      }

    }

  }

  return answer;

}

template <typename U , U a_U(const U&,const U&) , const U& z_U() , U m_U(const U&,const U&) , int size_max> int FastZetaTransform<U,a_U,z_U,m_U,size_max>::Moevius( const int& t0 , const int& t1 )
{

  int t = t1 ^ t0;
  int count = 0;
  
  while( t != 0 ){

    t -= t & -t;
    count++;

  }
  
  return ( count & 1 ) == 0 ? 1 : -1;

}


inline DEXPR( int , bound_Ai , 1000000 , 100 );
inline list<int> E( const int& i )
{

  cerr << "ここが呼ばれるのは意図通りではありません。" << endl;
  abort();
  list<int> answer{};
  int n = 0;
  while( n <= bound_Ai ){
    answer.push_back( n );
    n += i;
  }
  return answer;
}

template <typename INT , INT val_limit , int length_max = val_limit>
class PrimeEnumeration
{

public:
  INT m_val[length_max];
  int m_length;
  inline constexpr PrimeEnumeration();

};

template <typename INT , INT val_limit , int length_max>
inline constexpr PrimeEnumeration<INT,val_limit,length_max>::PrimeEnumeration() : m_val() , m_length( 0 )
{

  bool is_comp[val_limit] = {};

  for( INT i = 2 ; i < val_limit ; i++ ){

    if( is_comp[i] == false ){

      INT j = i;

      while( ( j += i ) < val_limit ){

	is_comp[j] = true;

      }

      m_val[m_length++] = i;

      if( m_length >= length_max ){

	break;
	
      }

    }

  }

}

  template <typename INT , INT val_limit , int length_max>
void SetPrimeFactorisation( const PrimeEnumeration<INT,val_limit,length_max>& prime , const INT& n , vector<INT>& P , vector<INT>& exponent )
{

  INT n_copy = n;
  int i = 0;

  while( i < prime.m_length ){

    const INT& p = prime.m_val[i];

    if( p * p > n_copy ){

      break;
      
    }
    
    if( n_copy % p == 0 ){

      P.push_back( p );
      exponent.push_back( 1 );
      INT& exponent_back = exponent.back();
      n_copy /= p;
    
      while( n_copy % p == 0 ){

	exponent_back++;
	n_copy /= p;
      
      }

    }
    
    i++;

  }

  if( n_copy != 1 ){

    P.push_back( n_copy );
    exponent.push_back( 1 );
    
  }
  
  return;

}

template <typename INT>
void SetPrimeFactorisation( const INT& n , vector<INT>& P , vector<INT>& exponent , vector<INT>& P_power )
{

  INT n_copy = n;
  INT p = 2;

  if( n_copy % p == 0 ){

    P.push_back( p );
    exponent.push_back( 1 );
    P_power.push_back( p );
    INT& exponent_back = exponent.back();
    INT& P_power_back = P_power.back();
    n_copy /= p;
    
    while( n_copy % p == 0 ){

      exponent_back++;
      P_power_back *= p;
      n_copy /= p;
      
    }

  }

  p++;

  while( p * p <= n_copy ){

    if( n_copy % p == 0 ){

      P.push_back( p );
      exponent.push_back( 1 );
      P_power.push_back( p );
      INT& exponent_back = exponent.back();
      INT& P_power_back = P_power.back();
      n_copy /= p;
    
      while( n_copy % p == 0 ){

	exponent_back++;
	P_power_back *= p;
	n_copy /= p;
      
      }

    }

    p += 2;

  }

  if( n_copy != 1 ){

    P.push_back( n_copy );
    exponent.push_back( 1 );
    
  }
  
  return;

}

// sqrt( n )以下の最大の素数 < val_limit の時のみサポート。
template <typename INT , INT val_limit , int length_max>
list<int> EnumerateDivisor( const PrimeEnumeration<INT,val_limit,length_max>& prime , INT n ) noexcept
{

  vector<INT> P{};
  vector<INT> exponent{};
  SetPrimeFactorisation( prime , n , P , exponent );
  const int length = P.size();
  
  list<INT> divisor{};
  divisor.push_back( 1 );
  auto begin = divisor.begin() , end = divisor.end();
  
  for( int i = 0 ; i < length ; i++ ){

    const INT& P_i = P[i];
    const int& exponent_i = exponent[i];
    list<int> temp{};
    INT power = 1;
    
    for( int e = 1 ; e <= exponent_i ; e++ ){

      power *= P_i;

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

	temp.push_back( *itr * power );

      }
      
    }
    
    while( ! temp.empty() ){

      divisor.push_back( temp.front() );
      temp.pop_front();

    }
    
  }

  return divisor;

}

inline CEXPR( int , sqrt_bound_Ai , 1000 );
inline constexpr PrimeEnumeration<int,sqrt_bound_Ai,sqrt_bound_Ai> prime{};

inline list<int> E_inv( const int& i ) { list<int> answer = EnumerateDivisor( prime , i ); answer.pop_back(); return answer; }

int Ai;
inline int id( const int& i ) { return i; }
inline list<int> r( const int& n )
{

  vector<int> P{};
  vector<int> exponent{};
  SetPrimeFactorisation( prime , Ai , P , exponent );
  const int length = P.size();
  
  list<int> sqfr_divisor{};
  sqfr_divisor.push_back( 1 );
  auto begin = sqfr_divisor.begin() , end = sqfr_divisor.end();
  
  for( int i = 0 ; i < length ; i++ ){

    const int& P_i = P[i];
    list<int> temp{};
    
    for( auto itr = begin ; itr != end ; itr++ ){

      temp.push_back( *itr * P_i );

    }
    
    while( ! temp.empty() ){

      sqfr_divisor.push_back( temp.front() );
      temp.pop_front();

    }
    
  }

  return sqfr_divisor;

}

template <typename INT , INT val_limit , int length_max>
int MoeviusFunction( const PrimeEnumeration<INT,val_limit,length_max>& prime , INT n ) noexcept
{

  static int memory[bound_Ai + 1] = {};
  static bool uninitialised = true;

  if( uninitialised ){

    for( int i = 0 ; i < bound_Ai + 1 ; i++ ){

      memory[i] = -2;

    }

    uninitialised = false;

  }
  
  int& answer = memory[n];

  if( answer == -2 ){

    answer = 1;
    int i = 0;

    while( i < prime.m_length && n > 1 ){

      const int& p = prime.m_val[i];

      if( n % p == 0 ){

	n /= p;

	if( n % p == 0 ){

	  return answer = 0;

	}

	answer *= -1;

      }

      i++;

    }

    n == 1 ? answer : answer *= -1;

  }

  return answer;

}

inline int mu( const int& t0 , const int& t1 ) { return MoeviusFunction( prime , t0 / t1 ); }

US ull = unsigned long long;IN CEXPR(uint,P,998244353);TE <uint M,TY INT> IN CE INT& RS(INT& n)NE{RE n < 0?((((++n)*= -1)%= M)*= -1)+= M - 1:n %= M;}TE <uint M> IN CE uint& RS(uint& n)NE{RE n %= M;}TE <uint M> IN CE ull& RS(ull& n)NE{RE n %= M;}TE <TY INT> IN CE INT& RSP(INT& n)NE{CE CO uint trunc = (1 << 23)- 1;INT n_u = n >> 23;n &= trunc;INT n_uq = (n_u / 7)/ 17;n_u -= n_uq * 119;n += n_u << 23;RE n < n_uq?n += P - n_uq:n -= n_uq;}TE <> IN CE ull& RS<P,ull>(ull& n)NE{CE CO ull Pull = P;CE CO ull Pull2 = (Pull - 1)* (Pull - 1);RE RSP(n > Pull2?n -= Pull2:n);}TE <uint M,TY INT> IN CE INT RS(INT&& n)NE{RE MO(RS<M>(n));}TE <uint M,TY INT> IN CE INT RS(CO INT& n)NE{RE RS<M>(INT(n));}

#define SFINAE_FOR_MOD(DEFAULT)TY T,enable_if_t<is_constructible<uint,decay_t<T> >::value>* DEFAULT
#define DC_OF_CM_FOR_MOD(FUNC)IN bool OP FUNC(CO Mod<M>& n)CO NE
#define DC_OF_AR_FOR_MOD(FUNC)IN Mod<M> OP FUNC(CO Mod<M>& n)CO NE;TE <SFINAE_FOR_MOD(= nullptr)> IN Mod<M> OP FUNC(T&& n)CO NE;
#define DF_OF_CM_FOR_MOD(FUNC)TE <uint M> IN bool Mod<M>::OP FUNC(CO Mod<M>& n)CO NE{RE m_n FUNC n.m_n;}
#define DF_OF_AR_FOR_MOD(FUNC,FORMULA)TE <uint M> IN Mod<M> Mod<M>::OP FUNC(CO Mod<M>& n)CO NE{RE MO(Mod<M>(*TH)FUNC ## = n);}TE <uint M> TE <SFINAE_FOR_MOD()> IN Mod<M> Mod<M>::OP FUNC(T&& n)CO NE{RE FORMULA;}TE <uint M,SFINAE_FOR_MOD(= nullptr)> IN Mod<M> OP FUNC(T&& n0,CO Mod<M>& n1)NE{RE MO(Mod<M>(forward<T>(n0))FUNC ## = n1);}

TE <uint M>CL Mod{PU:uint m_n;IN CE Mod()NE;IN CE Mod(CO Mod<M>& n)NE;IN CE Mod(Mod<M>& n)NE;IN CE Mod(Mod<M>&& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> IN CE Mod(CO T& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> IN CE Mod(T& n)NE;TE <SFINAE_FOR_MOD(= nullptr)> IN CE Mod(T&& n)NE;IN CE Mod<M>& OP=(CO Mod<M>& n)NE;IN CE Mod<M>& OP=(Mod<M>&& n)NE;IN CE Mod<M>& OP+=(CO Mod<M>& n)NE;IN CE Mod<M>& OP-=(CO Mod<M>& n)NE;IN CE Mod<M>& OP*=(CO Mod<M>& n)NE;IN Mod<M>& OP/=(CO Mod<M>& n);IN CE Mod<M>& OP<<=(int n)NE;IN CE Mod<M>& OP>>=(int n)NE;IN CE Mod<M>& OP++()NE;IN CE Mod<M> OP++(int)NE;IN CE Mod<M>& OP--()NE;IN CE Mod<M> OP--(int)NE;DC_OF_CM_FOR_MOD(==);DC_OF_CM_FOR_MOD(!=);DC_OF_CM_FOR_MOD(<);DC_OF_CM_FOR_MOD(<=);DC_OF_CM_FOR_MOD(>);DC_OF_CM_FOR_MOD(>=);DC_OF_AR_FOR_MOD(+);DC_OF_AR_FOR_MOD(-);DC_OF_AR_FOR_MOD(*);DC_OF_AR_FOR_MOD(/);IN CE Mod<M> OP<<(int n)CO NE;IN CE Mod<M> OP>>(int n)CO NE;IN CE Mod<M> OP-()CO NE;IN CE Mod<M>& SignInvert()NE;IN CE Mod<M>& Double()NE;IN CE Mod<M>& Halve()NE;IN Mod<M>& Invert();TE <TY T> IN CE Mod<M>& PositivePW(T&& EX)NE;TE <TY T> IN CE Mod<M>& NonNegativePW(T&& EX)NE;TE <TY T> IN CE Mod<M>& PW(T&& EX);IN CE VO swap(Mod<M>& n)NE;IN CE CO uint& RP()CO NE;ST IN CE Mod<M> DeRP(CO uint& n)NE;ST IN CE uint& Normalise(uint& n)NE;ST IN CO Mod<M>& Inverse(CO uint& n)NE;ST IN CO Mod<M>& Factorial(CO uint& n)NE;ST IN CO Mod<M>& FactorialInverse(CO uint& n)NE;ST IN CO Mod<M>& zero()NE;ST IN CO Mod<M>& one()NE;TE <TY T> IN CE Mod<M>& Ref(T&& n)NE;};

#define SFINAE_FOR_MN(DEFAULT)TY T,enable_if_t<is_constructible<Mod<M>,decay_t<T> >::value>* DEFAULT
#define DC_OF_AR_FOR_MN(FUNC)IN MN<M> OP FUNC(CO MN<M>& n)CO NE;TE <SFINAE_FOR_MOD(= nullptr)> IN MN<M> OP FUNC(T&& n)CO NE;
#define DF_OF_CM_FOR_MN(FUNC)TE <uint M> IN bool MN<M>::OP FUNC(CO MN<M>& n)CO NE{RE m_n FUNC n.m_n;}
#define DF_OF_AR_FOR_MN(FUNC,FORMULA)TE <uint M> IN MN<M> MN<M>::OP FUNC(CO MN<M>& n)CO NE{RE MO(MN<M>(*TH)FUNC ## = n);}TE <uint M> TE <SFINAE_FOR_MOD()> IN MN<M> MN<M>::OP FUNC(T&& n)CO NE{RE FORMULA;}TE <uint M,SFINAE_FOR_MOD(= nullptr)> IN MN<M> OP FUNC(T&& n0,CO MN<M>& n1)NE{RE MO(MN<M>(forward<T>(n0))FUNC ## = n1);}

TE <uint M>CL MN :PU Mod<M>{PU:IN CE MN()NE;IN CE MN(CO MN<M>& n)NE;IN CE MN(MN<M>& n)NE;IN CE MN(MN<M>&& n)NE;TE <SFINAE_FOR_MN(= nullptr)> IN CE MN(CO T& n)NE;TE <SFINAE_FOR_MN(= nullptr)> IN CE MN(T&& n)NE;IN CE MN<M>& OP=(CO MN<M>& n)NE;IN CE MN<M>& OP=(MN<M>&& n)NE;IN CE MN<M>& OP+=(CO MN<M>& n)NE;IN CE MN<M>& OP-=(CO MN<M>& n)NE;IN CE MN<M>& OP*=(CO MN<M>& n)NE;IN MN<M>& OP/=(CO MN<M>& n);IN CE MN<M>& OP<<=(int n)NE;IN CE MN<M>& OP>>=(int n)NE;IN CE MN<M>& OP++()NE;IN CE MN<M> OP++(int)NE;IN CE MN<M>& OP--()NE;IN CE MN<M> OP--(int)NE;DC_OF_AR_FOR_MN(+);DC_OF_AR_FOR_MN(-);DC_OF_AR_FOR_MN(*);DC_OF_AR_FOR_MN(/);IN CE MN<M> OP<<(int n)CO NE;IN CE MN<M> OP>>(int n)CO NE;IN CE MN<M> OP-()CO NE;IN CE MN<M>& SignInvert()NE;IN CE MN<M>& Double()NE;IN CE MN<M>& Halve()NE;IN CE MN<M>& Invert();TE <TY T> IN CE MN<M>& PositivePW(T&& EX)NE;TE <TY T> IN CE MN<M>& NonNegativePW(T&& EX)NE;TE <TY T> IN CE MN<M>& PW(T&& EX);IN CE uint RP()CO NE;IN CE Mod<M> Reduce()CO NE;ST IN CE MN<M> DeRP(CO uint& n)NE;ST IN CO MN<M>& Formise(CO uint& n)NE;ST IN CO MN<M>& Inverse(CO uint& n)NE;ST IN CO MN<M>& Factorial(CO uint& n)NE;ST IN CO MN<M>& FactorialInverse(CO uint& n)NE;ST IN CO MN<M>& zero()NE;ST IN CO MN<M>& one()NE;ST IN CE uint Form(CO uint& n)NE;ST IN CE ull& Reduction(ull& n)NE;ST IN CE ull& ReducedMU(ull& n,CO uint& m)NE;ST IN CE uint MU(CO uint& n0,CO uint& n1)NE;ST IN CE uint BaseSquareTruncation(uint& n)NE;TE <TY T> IN CE MN<M>& Ref(T&& n)NE;};TE <uint M> IN CE MN<M> Twice(CO MN<M>& n)NE;TE <uint M> IN CE MN<M> Half(CO MN<M>& n)NE;TE <uint M> IN CE MN<M> Inverse(CO MN<M>& n);TE <uint M,TY T> IN CE MN<M> PW(CO MN<M>& n,CO T& EX);TE <TY T> IN CE MN<2> PW(CO MN<2>& n,CO T& p);TE <TY T> IN CE T Square(CO T& t);TE <> IN CE MN<2> Square<MN<2> >(CO MN<2>& t);TE <uint M> IN CE VO swap(MN<M>& n0,MN<M>& n1)NE;TE <uint M> IN string to_string(CO MN<M>& n)NE;TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO MN<M>& n);

TE <uint M>CL COantsForMod{PU:COantsForMod()= delete;ST CE CO bool g_even = ((M & 1)== 0);ST CE CO uint g_memory_bound = 1000000;ST CE CO uint g_memory_LE = M < g_memory_bound?M:g_memory_bound;ST IN CE ull MNBasePW(ull&& EX)NE;ST CE uint g_M_minus = M - 1;ST CE uint g_M_minus_2 = M - 2;ST CE uint g_M_minus_2_neg = 2 - M;ST CE CO int g_MN_digit = 32;ST CE CO ull g_MN_base = ull(1)<< g_MN_digit;ST CE CO uint g_MN_base_minus = uint(g_MN_base - 1);ST CE CO uint g_MN_digit_half = (g_MN_digit + 1)>> 1;ST CE CO uint g_MN_base_sqrt_minus = (1 << g_MN_digit_half)- 1;ST CE CO uint g_MN_M_neg_inverse = uint((g_MN_base - MNBasePW((ull(1)<< (g_MN_digit - 1))- 1))& g_MN_base_minus);ST CE CO uint g_MN_base_mod = uint(g_MN_base % M);ST CE CO uint g_MN_base_square_mod = uint(((g_MN_base % M)* (g_MN_base % M))% M);};TE <uint M> IN CE ull COantsForMod<M>::MNBasePW(ull&& EX)NE{ull prod = 1;ull PW = M;WH(EX != 0){(EX & 1)== 1?(prod *= PW)&= g_MN_base_minus:prod;EX >>= 1;(PW *= PW)&= g_MN_base_minus;}RE prod;}

#include <immintrin.h>
#define SET_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR0,SCALAR1,SCALAR2,SCALAR3)CE CO UINT VE_NAME ## _copy[4] ={SCALAR0,SCALAR1,SCALAR2,SCALAR3};ST CO __m128i v_ ## VE_NAME = _mm_load_si128((__m128i*)VE_NAME ##_copy)
#define SET_VE_64_128_FOR_SIMD(UINT,VE_NAME,SCALAR0,SCALAR1)CE CO UINT VE_NAME ## _copy[2] ={SCALAR0,SCALAR1};ST CO __m128i v_ ## VE_NAME = _mm_load_si128((__m128i*)VE_NAME ##_copy)
#define SET_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR0,SCALAR1,SCALAR2,SCALAR3)CE CO ULL VE_NAME ## _copy[4] ={SCALAR0,SCALAR1,SCALAR2,SCALAR3};ST CO __m256i v_ ## VE_NAME = _mm256_load_si256((__m256i*)VE_NAME ##_copy)
#define SET_CO_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR)SET_VE_32_128_FOR_SIMD(UINT,VE_NAME,SCALAR,SCALAR,SCALAR,SCALAR)
#define SET_CO_VE_64_128_FOR_SIMD(ULL,VE_NAME,SCALAR)SET_VE_64_128_FOR_SIMD(ULL,VE_NAME,SCALAR,SCALAR)
#define SET_CO_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR)SET_VE_64_256_FOR_SIMD(ULL,VE_NAME,SCALAR,SCALAR,SCALAR,SCALAR)

TE <uint M>CL COantsForSIMDForMod{PU:COantsForSIMDForMod()= delete;ST IN CO __m128i& v_M()NE;ST IN CO __m128i& v_Mull()NE;ST IN CO __m128i& v_M_minus()NE;ST IN CO __m128i& v_M_neg_inverse()NE;ST IN CO __m128i& v_digitull()NE;};TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M,M);RE v_M;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_Mull()NE{SET_CO_VE_64_128_FOR_SIMD(ull,Mull,M);RE v_Mull;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M_minus()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M_minus,M - 1);RE v_M_minus;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_M_neg_inverse()NE{SET_CO_VE_32_128_FOR_SIMD(uint,M_neg_inverse,COantsForMod<M>::g_MN_M_neg_inverse);RE v_M_neg_inverse;}TE <uint M> IN CO __m128i& COantsForSIMDForMod<M>::v_digitull()NE{SET_CO_VE_64_128_FOR_SIMD(ull,digitull,COantsForMod<M>::g_MN_digit);RE v_digitull;}TE <uint M> IN __m128i& SIMD_RS_32_128(__m128i& v)NE{CO __m128i& v_M = COantsForSIMDForMod<M>::v_M();RE v -= v_M * _mm_cmpgt_epi32(v,v_M);}TE <uint M> IN __m128i& SIMD_RS_64_128(__m128i& v)NE{ull v_copy[2];_mm_store_si128((__m128i*)v_copy,v);for(uint i = 0;i < 2;i++){ull& v_copy_i = v_copy[i];v_copy_i = (v_copy_i < M?0:M);}RE v -= _mm_load_si128((__m128i*)v_copy);}TE <uint M> IN __m256i& SIMD_RS_64_256(__m256i& v)NE{ull v_copy[4];_mm256_store_si256((__m256i*)v_copy,v);for(uint i = 0;i < 4;i++){ull& v_copy_i = v_copy[i];v_copy_i = (v_copy_i < M?0:M);}RE v -= _mm256_load_si256((__m256i*)v_copy);}IN CE int SIMD_Shuffle(CRI a0,CRI a1,CRI a2,CRI a3)NE{RE (a0 << (0 << 1))+ (a1 << (1 << 1))+ (a2 << (2 << 1))+ (a3 << (3 << 1));}TE <uint M> IN VO SIMD_Addition_32_64(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& b0,CO Mod<M>& b1,Mod<M>& c0,Mod<M>& c1)NE{uint a_copy[4] ={a0.m_n,a1.m_n,0,0};uint b_copy[4] ={b0.m_n,b1.m_n,0,0};__m128i v_a = _mm_load_si128((__m128i*)a_copy);v_a += _mm_load_si128((__m128i*)b_copy);ST CO __m128i& v_M_minus = COantsForSIMDForMod<M>::v_M_minus();ST CO __m128i& v_M = COantsForSIMDForMod<M>::v_M();v_a += _mm_cmpgt_epi32(v_a,v_M_minus)& v_M;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);RE;}TE <uint M> IN VO SIMD_Addition_32_128(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& a2,CO Mod<M>& a3,CO Mod<M>& b0,CO Mod<M>& b1,CO Mod<M>& b2,CO Mod<M>& b3,Mod<M>& c0,Mod<M>& c1,Mod<M>& c2,Mod<M>& c3)NE{uint a_copy[4] ={a0.m_n,a1.m_n,a2.m_n,a3.m_n};uint b_copy[4] ={b0.m_n,b1.m_n,b2.m_n,b3.m_n};__m128i v_a = _mm_load_si128((__m128i*)a_copy)+ _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 4;i++){b_copy[i] = a_copy[i] < M?0:M;}v_a -= _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);c2.m_n = MO(a_copy[2]);c3.m_n = MO(a_copy[3]);RE;}TE <uint M> IN VO SIMD_Substracition_32_64(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& b0,CO Mod<M>& b1,Mod<M>& c0,Mod<M>& c1)NE{uint a_copy[4] ={a0.m_n,a1.m_n,0,0};uint b_copy[4] ={b0.m_n,b1.m_n,0,0};__m128i v_a = _mm_load_si128((__m128i*)a_copy);__m128i v_b = _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 2;i++){b_copy[i] = a_copy[i] < b_copy[i]?M:0;}(v_a += _mm_load_si128((__m128i*)b_copy))-= v_b;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);RE;}TE <uint M> IN VO SIMD_Subtraction_32_128(CO Mod<M>& a0,CO Mod<M>& a1,CO Mod<M>& a2,CO Mod<M>& a3,CO Mod<M>& b0,CO Mod<M>& b1,CO Mod<M>& b2,CO Mod<M>& b3,Mod<M>& c0,Mod<M>& c1,Mod<M>& c2,Mod<M>& c3)NE{uint a_copy[4] ={a0.m_n,a1.m_n,a2.m_n,a3.m_n};uint b_copy[4] ={b0.m_n,b1.m_n,b2.m_n,b3.m_n};__m128i v_a = _mm_load_si128((__m128i*)a_copy);__m128i v_b = _mm_load_si128((__m128i*)b_copy);_mm_store_si128((__m128i*)a_copy,v_a);for(uint i = 0;i < 4;i++){b_copy[i] = a_copy[i] < b_copy[i]?M:0;}(v_a += _mm_load_si128((__m128i*)b_copy))-= v_b;_mm_store_si128((__m128i*)a_copy,v_a);c0.m_n = MO(a_copy[0]);c1.m_n = MO(a_copy[1]);c2.m_n = MO(a_copy[2]);c3.m_n = MO(a_copy[3]);RE;}

US MP = Mod<P>;US MNP = MN<P>;TE <uint M> IN CE uint MN<M>::Form(CO uint& n)NE{ull n_copy = n;RE uint(MO(Reduction(n_copy *= COantsForMod<M>::g_MN_base_square_mod)));}TE <uint M> IN CE ull& MN<M>::Reduction(ull& n)NE{ull n_sub = n & COantsForMod<M>::g_MN_base_minus;RE ((n += ((n_sub *= COantsForMod<M>::g_MN_M_neg_inverse)&= COantsForMod<M>::g_MN_base_minus)*= M)>>= COantsForMod<M>::g_MN_digit)< M?n:n -= M;}TE <uint M> IN CE ull& MN<M>::ReducedMU(ull& n,CO uint& m)NE{RE Reduction(n *= m);}TE <uint M> IN CE uint MN<M>::MU(CO uint& n0,CO uint& n1)NE{ull n0_copy = n0;RE uint(MO(ReducedMU(ReducedMU(n0_copy,n1),COantsForMod<M>::g_MN_base_square_mod)));}TE <uint M> IN CE uint MN<M>::BaseSquareTruncation(uint& n)NE{CO uint n_u = n >> COantsForMod<M>::g_MN_digit_half;n &= COantsForMod<M>::g_MN_base_sqrt_minus;RE n_u;}TE <uint M> IN CE MN<M>::MN()NE:Mod<M>(){static_assert(! COantsForMod<M>::g_even);}TE <uint M> IN CE MN<M>::MN(CO MN<M>& n)NE:Mod<M>(n){}TE <uint M> IN CE MN<M>::MN(MN<M>& n)NE:Mod<M>(n){}TE <uint M> IN CE MN<M>::MN(MN<M>&& n)NE:Mod<M>(MO(n)){}TE <uint M> TE <SFINAE_FOR_MN()> IN CE MN<M>::MN(CO T& n)NE:Mod<M>(n){static_assert(! COantsForMod<M>::g_even);Mod<M>::m_n = Form(Mod<M>::m_n);}TE <uint M> TE <SFINAE_FOR_MN()> IN CE MN<M>::MN(T&& n)NE:Mod<M>(forward<T>(n)){static_assert(! COantsForMod<M>::g_even);Mod<M>::m_n = Form(Mod<M>::m_n);}TE <uint M> IN CE MN<M>& MN<M>::OP=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP=(n));}TE <uint M> IN CE MN<M>& MN<M>::OP=(MN<M>&& n)NE{RE Ref(Mod<M>::OP=(MO(n)));}TE <uint M> IN CE MN<M>& MN<M>::OP+=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP+=(n));}TE <uint M> IN CE MN<M>& MN<M>::OP-=(CO MN<M>& n)NE{RE Ref(Mod<M>::OP-=(n));}TE <uint M> IN CE MN<M>& MN<M>::OP*=(CO MN<M>& n)NE{ull m_n_copy = Mod<M>::m_n;RE Ref(Mod<M>::m_n = MO(ReducedMU(m_n_copy,n.m_n)));}TE <uint M> IN MN<M>& MN<M>::OP/=(CO MN<M>& n){RE OP*=(MN<M>(n).Invert());}TE <uint M> IN CE MN<M>& MN<M>::OP<<=(int n)NE{RE Ref(Mod<M>::OP<<=(n));}TE <uint M> IN CE MN<M>& MN<M>::OP>>=(int n)NE{RE Ref(Mod<M>::OP>>=(n));}TE <uint M> IN CE MN<M>& MN<M>::OP++()NE{RE Ref(Mod<M>::Normalise(Mod<M>::m_n += COantsForMod<M>::g_MN_base_mod));}TE <uint M> IN CE MN<M> MN<M>::OP++(int)NE{MN<M> n{*TH};OP++();RE n;}TE <uint M> IN CE MN<M>& MN<M>::OP--()NE{RE Ref(Mod<M>::m_n < COantsForMod<M>::g_MN_base_mod?((Mod<M>::m_n += M)-= COantsForMod<M>::g_MN_base_mod):Mod<M>::m_n -= COantsForMod<M>::g_MN_base_mod);}TE <uint M> IN CE MN<M> MN<M>::OP--(int)NE{MN<M> n{*TH};OP--();RE n;}DF_OF_AR_FOR_MN(+,MN<M>(forward<T>(n))+= *TH);DF_OF_AR_FOR_MN(-,MN<M>(forward<T>(n)).SignInvert()+= *TH);DF_OF_AR_FOR_MN(*,MN<M>(forward<T>(n))*= *TH);DF_OF_AR_FOR_MN(/,MN<M>(forward<T>(n)).Invert()*= *TH);TE <uint M> IN CE MN<M> MN<M>::OP<<(int n)CO NE{RE MO(MN<M>(*TH)<<= n);}TE <uint M> IN CE MN<M> MN<M>::OP>>(int n)CO NE{RE MO(MN<M>(*TH)>>= n);}TE <uint M> IN CE MN<M> MN<M>::OP-()CO NE{RE MO(MN<M>(*TH).SignInvert());}TE <uint M> IN CE MN<M>& MN<M>::SignInvert()NE{RE Ref(Mod<M>::m_n > 0?Mod<M>::m_n = M - Mod<M>::m_n:Mod<M>::m_n);}TE <uint M> IN CE MN<M>& MN<M>::Double()NE{RE Ref(Mod<M>::Double());}TE <uint M> IN CE MN<M>& MN<M>::Halve()NE{RE Ref(Mod<M>::Halve());}TE <uint M> IN CE MN<M>& MN<M>::Invert(){assert(Mod<M>::m_n > 0);RE PositivePW(uint(COantsForMod<M>::g_M_minus_2));}TE <uint M> TE <TY T> IN CE MN<M>& MN<M>::PositivePW(T&& EX)NE{MN<M> PW{*TH};(--EX)%= COantsForMod<M>::g_M_minus_2;WH(EX != 0){(EX & 1)== 1?OP*=(PW):*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <uint M> TE <TY T> IN CE MN<M>& MN<M>::NonNegativePW(T&& EX)NE{RE EX == 0?Ref(Mod<M>::m_n = 1):PositivePW(forward<T>(EX));}TE <uint M> TE <TY T> IN CE MN<M>& MN<M>::PW(T&& EX){bool neg = EX < 0;assert(!(neg && Mod<M>::m_n == 0));RE neg?PositivePW(forward<T>(EX *= COantsForMod<M>::g_M_minus_2_neg)):NonNegativePW(forward<T>(EX));}TE <uint M> IN CE uint MN<M>::RP()CO NE{ull m_n_copy = Mod<M>::m_n;RE MO(Reduction(m_n_copy));}TE <uint M> IN CE Mod<M> MN<M>::Reduce()CO NE{ull m_n_copy = Mod<M>::m_n;RE Mod<M>::DeRP(MO(Reduction(m_n_copy)));}TE <uint M> IN CE MN<M> MN<M>::DeRP(CO uint& n)NE{RE MN<M>(Mod<M>::DeRP(n));}TE <uint M> IN CO MN<M>& MN<M>::Formise(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = DeRP(LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::Inverse(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>(Mod<M>::Inverse(LE_curr));LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::Factorial(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;ST MN<M> val_curr{one()};MN<M> val_last{one()};WH(LE_curr <= n){memory[LE_curr++] = val_curr *= ++val_last;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::FactorialInverse(CO uint& n)NE{ST MN<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;ST MN<M> val_curr{one()};MN<M> val_last{one()};WH(LE_curr <= n){memory[LE_curr] = val_curr *= Inverse(LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO MN<M>& MN<M>::zero()NE{ST CE CO MN<M> z{};RE z;}TE <uint M> IN CO MN<M>& MN<M>::one()NE{ST CE CO MN<M> o{DeRP(1)};RE o;}TE <uint M> TE <TY T> IN CE MN<M>& MN<M>::Ref(T&& n)NE{RE *TH;}TE <uint M> IN CE MN<M> Twice(CO MN<M>& n)NE{RE MO(MN<M>(n).Double());}TE <uint M> IN CE MN<M> Half(CO MN<M>& n)NE{RE MO(MN<M>(n).Halve());}TE <uint M> IN CE MN<M> Inverse(CO MN<M>& n){RE MO(MN<M>(n).Invert());}TE <uint M,TY T> IN CE MN<M> PW(CO MN<M>& n,CO T& EX){RE MO(MN<M>(n).PW(T(EX)));}TE <uint M> IN CE VO swap(MN<M>& n0,MN<M>& n1)NE{n0.swap(n1);}TE <uint M> IN string to_string(CO MN<M>& n)NE{RE to_string(n.RP())+ " + MZ";}TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO MN<M>& n){RE os << n.RP();}

TE <uint M> IN CE Mod<M>::Mod()NE:m_n(){}TE <uint M> IN CE Mod<M>::Mod(CO Mod<M>& n)NE:m_n(n.m_n){}TE <uint M> IN CE Mod<M>::Mod(Mod<M>& n)NE:m_n(n.m_n){}TE <uint M> IN CE Mod<M>::Mod(Mod<M>&& n)NE:m_n(MO(n.m_n)){}TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod(CO T& n)NE:m_n(RS<M>(n)){}TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod(T& n)NE:m_n(RS<M>(decay_t<T>(n))){}TE <uint M> TE <SFINAE_FOR_MOD()> IN CE Mod<M>::Mod(T&& n)NE:m_n(RS<M>(forward<T>(n))){}TE <uint M> IN CE Mod<M>& Mod<M>::OP=(CO Mod<M>& n)NE{RE Ref(m_n = n.m_n);}TE <uint M> IN CE Mod<M>& Mod<M>::OP=(Mod<M>&& n)NE{RE Ref(m_n = MO(n.m_n));}TE <uint M> IN CE Mod<M>& Mod<M>::OP+=(CO Mod<M>& n)NE{RE Ref(Normalise(m_n += n.m_n));}TE <uint M> IN CE Mod<M>& Mod<M>::OP-=(CO Mod<M>& n)NE{RE Ref(m_n < n.m_n?(m_n += M)-= n.m_n:m_n -= n.m_n);}TE <uint M> IN CE Mod<M>& Mod<M>::OP*=(CO Mod<M>& n)NE{RE Ref(m_n = COantsForMod<M>::g_even?RS<M>(ull(m_n)* n.m_n):MN<M>::MU(m_n,n.m_n));}TE <> IN CE MP& MP::OP*=(CO MP& n)NE{ull m_n_copy = m_n;RE Ref(m_n = MO((m_n_copy *= n.m_n)< P?m_n_copy:RSP(m_n_copy)));}TE <uint M> IN Mod<M>& Mod<M>::OP/=(CO Mod<M>& n){RE OP*=(Mod<M>(n).Invert());}TE <uint M> IN CE Mod<M>& Mod<M>::OP<<=(int n)NE{WH(n-- > 0){Normalise(m_n <<= 1);}RE *TH;}TE <uint M> IN CE Mod<M>& Mod<M>::OP>>=(int n)NE{WH(n-- > 0){((m_n & 1)== 0?m_n:m_n += M)>>= 1;}RE *TH;}TE <uint M> IN CE Mod<M>& Mod<M>::OP++()NE{RE Ref(m_n < COantsForMod<M>::g_M_minus?++m_n:m_n = 0);}TE <uint M> IN CE Mod<M> Mod<M>::OP++(int)NE{Mod<M> n{*TH};OP++();RE n;}TE <uint M> IN CE Mod<M>& Mod<M>::OP--()NE{RE Ref(m_n == 0?m_n = COantsForMod<M>::g_M_minus:--m_n);}TE <uint M> IN CE Mod<M> Mod<M>::OP--(int)NE{Mod<M> n{*TH};OP--();RE n;}DF_OF_CM_FOR_MOD(==);DF_OF_CM_FOR_MOD(!=);DF_OF_CM_FOR_MOD(>);DF_OF_CM_FOR_MOD(>=);DF_OF_CM_FOR_MOD(<);DF_OF_CM_FOR_MOD(<=);DF_OF_AR_FOR_MOD(+,Mod<M>(forward<T>(n))+= *TH);DF_OF_AR_FOR_MOD(-,Mod<M>(forward<T>(n)).SignInvert()+= *TH);DF_OF_AR_FOR_MOD(*,Mod<M>(forward<T>(n))*= *TH);DF_OF_AR_FOR_MOD(/,Mod<M>(forward<T>(n)).Invert()*= *TH);TE <uint M> IN CE Mod<M> Mod<M>::OP<<(int n)CO NE{RE MO(Mod<M>(*TH)<<= n);}TE <uint M> IN CE Mod<M> Mod<M>::OP>>(int n)CO NE{RE MO(Mod<M>(*TH)>>= n);}TE <uint M> IN CE Mod<M> Mod<M>::OP-()CO NE{RE MO(Mod<M>(*TH).SignInvert());}TE <uint M> IN CE Mod<M>& Mod<M>::SignInvert()NE{RE Ref(m_n > 0?m_n = M - m_n:m_n);}TE <uint M> IN CE Mod<M>& Mod<M>::Double()NE{RE Ref(Normalise(m_n <<= 1));}TE <uint M> IN CE Mod<M>& Mod<M>::Halve()NE{RE Ref(((m_n & 1)== 0?m_n:m_n += M)>>= 1);}TE <uint M> IN Mod<M>& Mod<M>::Invert(){assert(m_n > 0);uint m_n_neg;RE m_n < COantsForMod<M>::g_memory_LE?Ref(m_n = Inverse(m_n).m_n):(m_n_neg = M - m_n < COantsForMod<M>::g_memory_LE)?Ref(m_n = M - Inverse(m_n_neg).m_n):PositivePW(uint(COantsForMod<M>::g_M_minus_2));}TE <> IN Mod<2>& Mod<2>::Invert(){assert(m_n > 0);RE *TH;}TE <uint M> TE <TY T> IN CE Mod<M>& Mod<M>::PositivePW(T&& EX)NE{Mod<M> PW{*TH};EX--;WH(EX != 0){(EX & 1)== 1?OP*=(PW):*TH;EX >>= 1;PW *= PW;}RE *TH;}TE <> TE <TY T> IN CE Mod<2>& Mod<2>::PositivePW(T&& EX)NE{RE *TH;}TE <uint M> TE <TY T> IN CE Mod<M>& Mod<M>::NonNegativePW(T&& EX)NE{RE EX == 0?Ref(m_n = 1):Ref(PositivePW(forward<T>(EX)));}TE <uint M> TE <TY T> IN CE Mod<M>& Mod<M>::PW(T&& EX){bool neg = EX < 0;assert(!(neg && m_n == 0));neg?EX *= COantsForMod<M>::g_M_minus_2_neg:EX;RE m_n == 0?*TH:(EX %= COantsForMod<M>::g_M_minus)== 0?Ref(m_n = 1):PositivePW(forward<T>(EX));}TE <uint M> IN CO Mod<M>& Mod<M>::Inverse(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={zero(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr].m_n = M - MN<M>::MU(memory[M % LE_curr].m_n,M / LE_curr);LE_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::Factorial(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>::Factorial(LE_curr).Reduce();LE_curr++;}RE memory[n];}TE <uint M> IN CO Mod<M>& Mod<M>::FactorialInverse(CO uint& n)NE{ST Mod<M> memory[COantsForMod<M>::g_memory_LE] ={one(),one()};ST uint LE_curr = 2;WH(LE_curr <= n){memory[LE_curr] = MN<M>::FactorialInverse(LE_curr).Reduce();LE_curr++;}RE memory[n];}TE <uint M> IN CE VO Mod<M>::swap(Mod<M>& n)NE{std::swap(m_n,n.m_n);}TE <uint M> IN CE CO uint& Mod<M>::RP()CO NE{RE m_n;}TE <uint M> IN CE Mod<M> Mod<M>::DeRP(CO uint& n)NE{Mod<M> n_copy{};n_copy.m_n = n;RE n_copy;}TE <uint M> IN CE uint& Mod<M>::Normalise(uint& n)NE{RE n < M?n:n -= M;}TE <uint M> IN CO Mod<M>& Mod<M>::zero()NE{ST CE CO Mod<M> z{};RE z;}TE <uint M> IN CO Mod<M>& Mod<M>::one()NE{ST CE CO Mod<M> o{DeRP(1)};RE o;}TE <uint M> TE <TY T> IN CE Mod<M>& Mod<M>::Ref(T&& n)NE{RE *TH;}TE <uint M> IN CE Mod<M> Twice(CO Mod<M>& n)NE{RE MO(Mod<M>(n).Double());}TE <uint M> IN CE Mod<M> Half(CO Mod<M>& n)NE{RE MO(Mod<M>(n).Halve());}TE <uint M> IN Mod<M> Inverse(CO Mod<M>& n){RE MO(Mod<M>(n).Invert());}TE <uint M> IN CE Mod<M> Inverse_COrexpr(CO uint& n)NE{RE MO(Mod<M>::DeRP(RS<M>(n)).NonNegativePW(M - 2));}TE <uint M,TY T> IN CE Mod<M> PW(CO Mod<M>& n,CO T& EX){RE MO(Mod<M>(n).PW(T(EX)));}TE <uint M> IN CE VO swap(Mod<M>& n0,Mod<M>& n1)NE{n0.swap(n1);}TE <uint M> IN string to_string(CO Mod<M>& n)NE{RE to_string(n.RP())+ " + MZ";}TE<uint M,CL Traits> IN basic_ostream<char,Traits>& OP<<(basic_ostream<char,Traits>& os,CO Mod<M>& n){RE os << n.RP();}

// using MOD = MP;
using MOD = MNP;

inline MOD Sum( const MOD& u0 , const MOD& u1 ) { return u0 + u1; };
inline const MOD& Zero() { return MOD::zero(); };
inline MOD Prod( const MOD& u0 , const MOD& u1 ) { return u0 * u1; };

int main()
{
  UNTIE;
  // LIBRARY_SEARCH;
  // CEXPR( int , bound_T , 200000 );
  // CIN_ASSERT( T , 1 , bound_T );
  CEXPR( int , bound_N , 200000 ); // 0が5個
  // CEXPR( ll , bound_N , 1000000000 ); // 0が9個
  // CEXPR( ll , bound_N , 1000000000000000000 ); // 0が18個
  // CEXPR( int , bound_M , 100000 ); // 0が5個
  // CEXPR( ll , bound_M , 1000000000 ); // 0が9個
  // CEXPR( ll , bound_M , 1000000000000000000 ); // 0が18個
  CIN_ASSERT( N , 1 , bound_N );
  EnumerationZetaTransform<int,E,E_inv,MOD,Sum,Zero,Prod,bound_Ai+1,id,id> zt{ bound_Ai + 1 };
  REPEAT( N ){
    SET_ASSERT( Ai , 1 , bound_Ai );
    zt.Add( Ai , 1 + zt.InitialSegmentSum( 1 ) - zt.InverseImageSum<int,id,r,mu>( 1 ) );
  }
  RETURN( zt.InitialSegmentSum( 1 ) );
}
0