結果
| 問題 | No.2075 GCD Subsequence |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2023-06-11 12:03:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 3,480 ms / 4,000 ms |
| コード長 | 55,073 bytes |
| コンパイル時間 | 4,931 ms |
| コンパイル使用メモリ | 332,208 KB |
| 実行使用メモリ | 15,400 KB |
| 最終ジャッジ日時 | 2024-06-11 00:59:16 |
| 合計ジャッジ時間 | 47,748 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 14 ms
15,232 KB |
| testcase_01 | AC | 13 ms
15,132 KB |
| testcase_02 | AC | 14 ms
15,232 KB |
| testcase_03 | AC | 13 ms
15,264 KB |
| testcase_04 | AC | 14 ms
15,232 KB |
| testcase_05 | AC | 14 ms
15,132 KB |
| testcase_06 | AC | 14 ms
15,264 KB |
| testcase_07 | AC | 15 ms
15,104 KB |
| testcase_08 | AC | 415 ms
15,360 KB |
| testcase_09 | AC | 588 ms
15,264 KB |
| testcase_10 | AC | 388 ms
15,272 KB |
| testcase_11 | AC | 495 ms
15,144 KB |
| testcase_12 | AC | 433 ms
15,272 KB |
| testcase_13 | AC | 331 ms
15,268 KB |
| testcase_14 | AC | 487 ms
15,268 KB |
| testcase_15 | AC | 348 ms
15,400 KB |
| testcase_16 | AC | 367 ms
15,272 KB |
| testcase_17 | AC | 577 ms
15,272 KB |
| testcase_18 | AC | 3,326 ms
15,272 KB |
| testcase_19 | AC | 3,337 ms
15,272 KB |
| testcase_20 | AC | 3,319 ms
15,272 KB |
| testcase_21 | AC | 3,364 ms
15,268 KB |
| testcase_22 | AC | 3,332 ms
15,148 KB |
| testcase_23 | AC | 3,328 ms
15,276 KB |
| testcase_24 | AC | 3,335 ms
15,396 KB |
| testcase_25 | AC | 3,310 ms
15,268 KB |
| testcase_26 | AC | 3,316 ms
15,272 KB |
| testcase_27 | AC | 3,357 ms
15,272 KB |
| testcase_28 | AC | 3,480 ms
15,268 KB |
| testcase_29 | AC | 14 ms
15,264 KB |
| testcase_30 | AC | 13 ms
15,132 KB |
ソースコード
#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 )
{
static int memory[bound_Ai + 1] = {};
static bool uninitialised = true;
if( uninitialised ){
for( int k = 1 ; k <= bound_Ai ; k++ ){
memory[k] = k;
}
for( int i = 0 ; i < prime.m_length ; i++ ){
const int& p_i = prime.m_val[i];
int div = bound_Ai / p_i;
for( int j = 1 ; j <= div ; j++ ){
int k = j * p_i;
int& memory_k = memory[k];
( memory_k == k ? k % p_i == 0 : false ) ? memory_k = p_i : memory_k;
}
}
uninitialised = false;
}
list<int> sqfr_divisor{};
sqfr_divisor.push_back( 1 );
auto begin_sqfr_divisor = sqfr_divisor.begin() , end_sqfr_divisor = sqfr_divisor.end();
int Ai_copy = Ai;
while( Ai_copy > 1 ){
const int& p = memory[Ai_copy];
while( ( Ai_copy /= p ) % p == 0 ){}
list<int> temp{};
for( auto itr_sqfr_divisor = begin_sqfr_divisor ; itr_sqfr_divisor != end_sqfr_divisor ; itr_sqfr_divisor++ ){
temp.push_back( *itr_sqfr_divisor * p );
}
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 ) );
}