// 手持ちのMod<998244353>のライブラリがバグってしまったのでデバッグ用提出。 #include using namespace std; using ll = long long; #define TYPE_OF( VAR ) decay_t #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr const 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 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 COUT( ANSWER ) cout << ( ANSWER ) << "\n"; #define QUIT return 0 #define RETURN( ANSWER ) COUT( ANSWER ); QUIT #define POWER( ANSWER , VAR , EXPONENT_REF , MODULO ) \ TYPE_OF( VAR ) ANSWER = 1; \ TYPE_OF( VAR ) VARIABLE_FOR_SQUARE_FOR_POWER = VAR; \ while( EXPONENT_REF != 0 ){ \ if( EXPONENT_REF % 2 == 1 ){ \ ANSWER = ( ANSWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO; \ } \ VARIABLE_FOR_SQUARE_FOR_POWER = ( VARIABLE_FOR_SQUARE_FOR_POWER * VARIABLE_FOR_SQUARE_FOR_POWER ) % MODULO; \ EXPONENT_REF /= 2; \ } template inline INT1& Residue( INT1& n , const INT2& M ) noexcept { return n >= 0 ? n %= M : ( ( ( ( ++n ) *= -1 ) %= M ) *= -1 ) += M - 1; } template inline INT1 Residue( INT1&& n , const INT2& M ) noexcept { return move( Residue( n , M ) ); } template inline INT1 Residue( const INT1& n , const INT2& M ) noexcept { return Residue( move( INT1( n ) ) , M ); } #define SFINAE_TYPE_FOR_MOD( TYPE ) \ decltype( INT_TYPE_FOR_MOD( decay_t() ) , TYPE() ) \ #define DECLARATION_OF_COMPARISON_FOR_MOD( FUNC ) \ inline bool operator FUNC( const Mod& n ) const noexcept \ #define DECLARATION_OF_ARITHMETIC_FOR_MOD( FUNC ) \ inline Mod operator FUNC( const Mod& n ) const noexcept; \ template inline SFINAE_TYPE_FOR_MOD( Mod ) operator FUNC( T&& n ) const noexcept; \ #define DEFINITION_OF_COMPARISON_FOR_MOD( FUNC ) \ template inline bool Mod::operator FUNC( const Mod& n ) const noexcept { return m_n FUNC n.m_n; } \ #define DEFINITION_OF_ARITHMETIC_FOR_MOD( FUNC , FORMULA ) \ template inline Mod Mod::operator FUNC( const Mod& n ) const noexcept { return move( Mod( *this ) FUNC ## = n ); } \ template template inline SFINAE_TYPE_FOR_MOD( Mod ) Mod::operator FUNC( T&& n ) const noexcept { return FORMULA; } \ template inline SFINAE_TYPE_FOR_MOD( Mod ) operator FUNC( T&& n0 , const Mod& n1 ) noexcept { return move( Mod( forward( n0 ) ) FUNC ## = n1 ); } \ template using VLArray = list; using INT_TYPE_FOR_MOD = int; // using INT_TYPE_FOR_MOD = ll; // ここをtempate などにしてしまうとoperator+などを呼び出す際に型推論に失敗する。整数型を変えたい時はINT_TYPE_FOR_MODの型エイリアスを変更する。 template class Mod { protected: INT_TYPE_FOR_MOD m_n; public: inline Mod() noexcept; inline Mod( const Mod& n ) noexcept; inline Mod( Mod& n ) noexcept; // INT_TYPE_FOR_MODがintならば恐らく実行速度に影響しないが念のため。 inline Mod( Mod&& n ) noexcept; template inline Mod( T& n , SFINAE_TYPE_FOR_MOD( int ) dummy = 0 ) noexcept; template inline Mod( T&& n , SFINAE_TYPE_FOR_MOD( int ) dummy = 0 ) noexcept; inline Mod& operator=( const Mod& n ) noexcept; inline Mod& operator+=( const Mod& n ) noexcept; inline Mod& operator-=( const Mod& n ) noexcept; inline Mod& operator*=( const Mod& n ) noexcept; inline Mod& operator/=( const Mod& n ); inline Mod& operator++() noexcept; inline Mod operator++( int ) noexcept; inline Mod& operator--() noexcept; inline Mod operator--( int ) noexcept; DECLARATION_OF_COMPARISON_FOR_MOD( == ); DECLARATION_OF_COMPARISON_FOR_MOD( != ); DECLARATION_OF_COMPARISON_FOR_MOD( < ); DECLARATION_OF_COMPARISON_FOR_MOD( <= ); DECLARATION_OF_COMPARISON_FOR_MOD( > ); DECLARATION_OF_COMPARISON_FOR_MOD( >= ); DECLARATION_OF_ARITHMETIC_FOR_MOD( + ); DECLARATION_OF_ARITHMETIC_FOR_MOD( - ); DECLARATION_OF_ARITHMETIC_FOR_MOD( * ); DECLARATION_OF_ARITHMETIC_FOR_MOD( / ); inline Mod operator-() const noexcept; inline Mod& SignInvert() noexcept; // Mが素数である場合のみサポート。 inline Mod& Invert(); template inline Mod& PositivePower( T&& exponent ) noexcept; // Mが素数であるかexponent>=0である場合にのみサポート。 template inline Mod& Power( T&& exponent ); inline const INT_TYPE_FOR_MOD& Represent() const noexcept; inline void swap( Mod& n ) noexcept; // Mが素数かつn < g_memory_lengthである場合のみサポート。 static inline const INT_TYPE_FOR_MOD& Inverse( const INT_TYPE_FOR_MOD& n ) noexcept; // n < g_memory_lengthである場合のみサポート。 static inline const INT_TYPE_FOR_MOD& Factorial( const INT_TYPE_FOR_MOD& n ) noexcept; // Mが素数かつn < g_memory_lengthである場合のみサポート。 static inline const INT_TYPE_FOR_MOD& FactorialInverse( const INT_TYPE_FOR_MOD& n ) noexcept; static inline const Mod& zero() noexcept; static inline const Mod& one() noexcept; private: static inline constexpr int BinaryDigitUpperBound() noexcept; static inline constexpr ll MontgomeryBasePower( INT_TYPE_FOR_MOD&& exponent ) noexcept; static constexpr const int g_Montgomery_digit = BinaryDigitUpperBound(); static constexpr const ll g_Montgomery_base = ll( 1 ) << g_Montgomery_digit; static constexpr const ll g_Montgomery_base_minus = g_Montgomery_base - 1; static constexpr const ll g_Montgomery_M_negative_inverse = g_Montgomery_base - MontgomeryBasePower( ( 1 << ( g_Montgomery_digit - 1 ) ) - 1 ); static constexpr const ll g_Montgomery_base_square = ( g_Montgomery_base * g_Montgomery_base ) % M; static constexpr const INT_TYPE_FOR_MOD g_memory_bound = 1000000; static constexpr const INT_TYPE_FOR_MOD g_memory_length = M < g_memory_bound ? M : g_memory_bound; static inline ll MontgomeryTranformation( const INT_TYPE_FOR_MOD& n ) noexcept; static inline ll& MontgomeryReduction( ll& n ) noexcept; static inline INT_TYPE_FOR_MOD MontgomeryMultiplication( const INT_TYPE_FOR_MOD& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept; static inline void Normalise( INT_TYPE_FOR_MOD& n ) noexcept; }; // Mが素数である場合にのみサポート。 template Mod inline Inverse( const Mod& n ); // Mが素数であるかexponent>=0である場合にのみサポート。 template inline Mod Power( const Mod& n , const T& exponent ); template inline Mod<2> Power( const Mod<2>& n , const T& p ); // ../Power/a_Body.hppにて定義。 template inline T Square( const T& t ); template <> inline Mod<2> Square >( const Mod<2>& t ); template inline void swap( Mod& n0 , Mod& n1 ) noexcept; template inline string to_string( const Mod& n ) noexcept; template inline basic_ostream& operator<<( basic_ostream& os , const Mod& n ); template inline constexpr int Mod::BinaryDigitUpperBound() noexcept { int answer = 0; ll power = 1; while( M > power ){ answer++; power <<= 1; } return answer; } template inline constexpr ll Mod::MontgomeryBasePower( INT_TYPE_FOR_MOD&& exponent ) noexcept { ll prod = 1; ll power = M; while( exponent != 0 ){ if( ( exponent & 1 ) == 1 ){ ( prod *= power ) &= g_Montgomery_base_minus; } ( power *= power ) &= g_Montgomery_base_minus; exponent >>= 1; } return prod; } template inline ll Mod::MontgomeryTranformation( const INT_TYPE_FOR_MOD& n ) noexcept { ll n_copy = n; return move( MontgomeryReduction( n_copy *= g_Montgomery_base_square ) ); } template inline ll& Mod::MontgomeryReduction( ll& n ) noexcept { ll n_copy = n; return ( ( n += ( ( ( n_copy &= g_Montgomery_base_minus ) *= g_Montgomery_M_negative_inverse ) &= g_Montgomery_base_minus ) *= M ) >>= g_Montgomery_digit ) < M ? n : n -= M; } template inline INT_TYPE_FOR_MOD Mod::MontgomeryMultiplication( const INT_TYPE_FOR_MOD& n0 , const INT_TYPE_FOR_MOD& n1 ) noexcept { ll n0_copy = n0; return MontgomeryReduction( MontgomeryReduction( n0_copy *= n1 ) *= g_Montgomery_base_square ); } template inline void Mod::Normalise( INT_TYPE_FOR_MOD& n ) noexcept { if( n >= M ){ n -= M; } else if( n < 0 ){ n += M; } } template inline Mod::Mod() noexcept : m_n() {} template inline Mod::Mod( const Mod& n ) noexcept : m_n( n.m_n ) {} template inline Mod::Mod( Mod& n ) noexcept : m_n( n.m_n ) {} template inline Mod::Mod( Mod&& n ) noexcept : m_n( move( n.m_n ) ) {} // nの書き換えを防ぐために明示的にキャスト template template inline Mod::Mod( T& n , SFINAE_TYPE_FOR_MOD( int ) dummy ) noexcept : m_n( Residue( INT_TYPE_FOR_MOD( n ) , M ) ) {} template template inline Mod::Mod( T&& n , SFINAE_TYPE_FOR_MOD( int ) dummy ) noexcept : m_n( Residue( forward( n ) , M ) ) {} template inline Mod& Mod::operator=( const Mod& n ) noexcept { m_n = n.m_n; return *this; } template inline Mod& Mod::operator+=( const Mod& n ) noexcept { Normalise( m_n += n.m_n ); return *this; } template inline Mod& Mod::operator-=( const Mod& n ) noexcept { Normalise( m_n -= n.m_n ); return *this; } template inline Mod& Mod::operator*=( const Mod& n ) noexcept { m_n = MontgomeryMultiplication( m_n , n.m_n ); return *this; } template inline Mod& Mod::operator/=( const Mod& n ) { return operator*=( Mod( n ).Invert() ); } template inline Mod& Mod::operator++() noexcept { return operator+=( one() ); } template inline Mod Mod::operator++( int ) noexcept { Mod n{ *this }; operator++(); return n; } template inline Mod& Mod::operator--() noexcept { return operator-=( one() ); } template inline Mod Mod::operator--( int ) noexcept { Mod n{ *this }; operator--(); return n; } DEFINITION_OF_COMPARISON_FOR_MOD( == ); DEFINITION_OF_COMPARISON_FOR_MOD( != ); DEFINITION_OF_COMPARISON_FOR_MOD( > ); DEFINITION_OF_COMPARISON_FOR_MOD( >= ); DEFINITION_OF_COMPARISON_FOR_MOD( < ); DEFINITION_OF_COMPARISON_FOR_MOD( <= ); DEFINITION_OF_ARITHMETIC_FOR_MOD( + , Mod( forward( n ) ) += *this ); DEFINITION_OF_ARITHMETIC_FOR_MOD( - , Mod( forward( n ) ).SignInvert() += *this ); DEFINITION_OF_ARITHMETIC_FOR_MOD( * , Mod( forward( n ) ) *= *this ); DEFINITION_OF_ARITHMETIC_FOR_MOD( / , Mod( forward( n ) ).Invert() *= *this ); template inline Mod Mod::operator-() const noexcept { return move( Mod( *this ).SignInvert() ); } template inline Mod& Mod::SignInvert() noexcept { if( m_n > 0 ){ m_n = M - m_n; } return *this; } template inline Mod& Mod::Invert() { assert( m_n > 0 ); if( m_n < g_memory_length ){ m_n = Inverse( m_n ); } else{ const INT_TYPE_FOR_MOD m_n_minus = M - m_n; if( m_n_minus < g_memory_length ){ m_n = M - Inverse( m_n_minus ); } else { return PositivePower( M - 2 ); } } return *this; } template template inline Mod& Mod::PositivePower( T&& exponent ) noexcept { ll prod = g_Montgomery_base; ll power = MontgomeryTranformation( m_n ); while( exponent != 0 ){ if( ( exponent & 1 ) == 1 ){ MontgomeryReduction( prod *= power ); } MontgomeryReduction( power *= power ); exponent >>= 1; } m_n = INT_TYPE_FOR_MOD( MontgomeryReduction( prod ) ); return *this; } template template inline Mod& Mod::Power( T&& exponent ) { if( exponent < 0 ){ assert( m_n != 0 ); exponent *= 2 - M; } exponent %= M - 1; if( exponent != 0 ){ return PositivePower( forward( exponent ) ); } return *this; } template inline const INT_TYPE_FOR_MOD& Mod::Inverse( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { -1 , 1 }; static int length_curr = 2; while( length_curr <= n ){ memory[length_curr] = M - MontgomeryMultiplication( memory[M % length_curr] , M / length_curr ); length_curr++; } return memory[n]; } template inline const INT_TYPE_FOR_MOD& Mod::Factorial( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { 1 , 1 }; static int length_curr = 2; static ll val_curr = g_Montgomery_base; while( length_curr <= n ){ memory[length_curr] = INT_TYPE_FOR_MOD( MontgomeryReduction( val_curr *= MontgomeryTranformation( length_curr ) ) ); length_curr++; } return memory[n]; } template inline const INT_TYPE_FOR_MOD& Mod::FactorialInverse( const INT_TYPE_FOR_MOD& n ) noexcept { static INT_TYPE_FOR_MOD memory[g_memory_length] = { 1 , 1 }; static int length_curr = 2; static ll val_curr = g_Montgomery_base; while( length_curr <= n ){ memory[length_curr] = INT_TYPE_FOR_MOD( MontgomeryReduction( val_curr *= MontgomeryTranformation( Inverse( length_curr ) ) ) ); length_curr++; } return memory[n]; } template inline const INT_TYPE_FOR_MOD& Mod::Represent() const noexcept { return m_n; } template inline void Mod::swap( Mod& n ) noexcept { std::swap( m_n , n.m_n ); } template inline const Mod& Mod::zero() noexcept { static const Mod z{}; return z; } template inline const Mod& Mod::one() noexcept { static const Mod o{ 1 }; return o; } template inline Mod Inverse( const Mod& n ) { return move( Mod( n ).Invert() ); } template inline Mod Power( const Mod& n , const T& exponent ) { return move( Mod( n ).Power( T( exponent ) ) ); } template inline Mod<2> Power( const Mod<2>& n , const T& exponent ) { return exponent == 0 ? Mod<2>::one() : n; } template <> inline Mod<2> Square >( const Mod<2>& t ) { return t; } template inline void swap( Mod& n0 , Mod& n1 ) noexcept { n0.swap( n1 ); } template inline string to_string( const Mod& n ) noexcept { return to_string( n.Represent() ) + " + MZ"; } template inline basic_ostream& operator<<( basic_ostream& os , const Mod& n ) { return os << n.Represent(); } // 以下は // https://yukicoder.me/submissions/803764 // のmain関数そのもの int main() { constexpr const ll bound_N = 1000000000000000000; CIN( ll , N ); assert( 1 <= N && N <= bound_N ); constexpr const int bound_M = 100000; CIN( int , M ); assert( 1 <= M && M <= bound_M ); if( N < M ){ RETURN( 0 ); } constexpr const ll P = 998244353; constexpr const ll two = 2; ll N_copy = N % ( P - 1 ); POWER( answer , two , N_copy , P ); ll inverse[bound_M]; inverse[1] = 1; N %= P; ll combination = N; answer--; if( M != 1 ){ answer = ( answer + P - N ) % P; } FOR( i , 2 , M ){ inverse[i] = P - ( inverse[P % i] * ( P / i ) ) % P; combination = ( combination * ( N + 1 + P - i ) ) % P; combination = ( combination * inverse[i] ) % P; answer = ( answer + P - combination ) % P; } RETURN( answer ); }