kpr/math/DynamicModInt.hpp

View this file on GitHub
Last update: 2023-06-23 11:13:58+09:00
Include: #include "kpr/math/DynamicModInt.hpp"

Depends on

Required by

Verified with

verify/yosupo/factorize.test.cpp

Code

#pragma once
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#include "../algorithm/Hash.hpp"
#include "../meta/constant.hpp"
#include "../meta/setting.hpp"
#include "../meta/trait.hpp"
#include "../io/in.hpp"
#include "../io/out.hpp"
#include "Montgomery.hpp"

namespace kpr {
    template<class T, std::size_t kind = 0, bool = false>
    struct DynamicModInt {
        static_assert(std::is_unsigned_v<T>, "The given type must be an unsigned integer type");

        using value_type = T;

    private:
        using larger_type = next_integer_t<T>;

        inline static Montgomery<T> montgomery;

    public:
        T value;

        static constexpr KYOPRO_BASE_INT get_kind() noexcept {
            return kind;
        }

        static void set_mod(T mod) noexcept {
            montgomery.set_mod(mod);
        }

        static KYOPRO_BASE_INT get_mod() noexcept {
            return montgomery.mod;
        }

        KYOPRO_BASE_INT get_val() noexcept {
            return montgomery.inv_transform(value);
        }

        DynamicModInt() noexcept = default;
        DynamicModInt(T value) noexcept: value(montgomery.transform(value % montgomery.mod + montgomery.mod)) {}

        template<class U>
        explicit operator U() const noexcept {
            return montgomery.inv_transform(value);
        }

        static DynamicModInt raw(T value) noexcept {
            DynamicModInt res;
            res.value = montgomery.transform(value);
            return res;
        }

        DynamicModInt pow(KYOPRO_BASE_UINT n) const noexcept {
            DynamicModInt res = 1, a = *this;
            while (n > 0) {
                if (n & 1) res = res * a;
                a = a * a;
                n >>= 1;
            }
            return res;
        }

        DynamicModInt inv() const noexcept {
            return pow(montgomery.mod - 2);
        }

        DynamicModInt operator +() const noexcept {
            return *this;
        }

        DynamicModInt operator -() const noexcept {
            return value == 0 ? 0 : montgomery.mod - value;
        }

        DynamicModInt& operator ++() noexcept {
            *this += DynamicModInt::raw(1);
            return *this;
        }

        DynamicModInt operator ++(int) noexcept {
            DynamicModInt before = *this;
            ++*this;
            return before;
        }

        DynamicModInt& operator --() noexcept {
            *this -= DynamicModInt::raw(1);
            return *this;
        }

        DynamicModInt operator --(int) noexcept {
            DynamicModInt before = *this;
            --*this;
            return before;
        }

        DynamicModInt& operator +=(DynamicModInt rhs) noexcept {
            if ((value += rhs.value - (montgomery.mod << 1)) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
            return *this;
        }

        DynamicModInt& operator -=(DynamicModInt rhs) noexcept {
            if ((value -= rhs.value) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
            return *this;
        }

        DynamicModInt& operator *=(DynamicModInt rhs) noexcept {
            value = montgomery.reduce(static_cast<larger_type>(value) * rhs.value);
            return *this;
        }

        DynamicModInt& operator /=(DynamicModInt rhs) noexcept {
            value = montgomery.reduce(static_cast<larger_type>(value) * rhs.inv().value);
            return *this;
        }

        friend DynamicModInt operator +(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs += rhs;
        }

        friend DynamicModInt operator -(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs -= rhs;
        }

        friend DynamicModInt operator *(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs *= rhs;
        }

        friend DynamicModInt operator /(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs /= rhs;
        }

        friend bool operator ==(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs.value == rhs.value;
        }

        friend bool operator !=(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs.value != rhs.value;
        }

        friend struct ScanFunction<DynamicModInt>;

        friend struct PrintFunction<DynamicModInt>;
    };

    template<class T, std::size_t kind>
    struct ScanFunction<DynamicModInt<T, kind>> {
        template<class Scanner>
        static void scan(Scanner& scanner, DynamicModInt<T, kind>& a) {
            std::int_fast64_t value;
            ScanFunction<std::int_fast64_t>::scan(scanner, value);
            a.value = a.montgomery.transform(value % a.montgomery.mod + a.montgomery.mod);
        }
    };

    template<class T, std::size_t kind>
    struct PrintFunction<DynamicModInt<T, kind>> {
        template<class Printer>
        static void print(Printer& printer, const DynamicModInt<T, kind>& a) {
            PrintFunction<T>::print(printer, a.montgomery.inv_transform(a.value));
        }
    };

    template<class T, std::size_t kind>
    struct Hash<DynamicModInt<T, kind>> {
        using value_type = DynamicModInt<T, kind>;

        std::size_t operator ()(DynamicModInt<T, kind> a) const noexcept {
            return static_cast<std::size_t>(a);
        }
    };
} // namespace kpr

#line 2 "kpr/math/DynamicModInt.hpp"
#include <cstddef>
#include <cstdint>
#include <limits>
#include <type_traits>
#line 3 "kpr/algorithm/Hash.hpp"
#include <functional>
#include <iterator>
#line 6 "kpr/algorithm/Hash.hpp"
#include <utility>
#line 4 "kpr/meta/tuple_like.hpp"
#include <tuple>
#line 6 "kpr/meta/tuple_like.hpp"

namespace kpr {
    namespace helper {
        struct CastableToAny {
            template<class T>
            operator T() const noexcept;
        };

        template<class T, std::size_t... idx, std::void_t<decltype(T{((void)idx, CastableToAny{})...})>* = nullptr>
        constexpr bool is_constructible_with(std::index_sequence<idx...>, bool) noexcept {
            return true;
        }
        template<class T, std::size_t... idx>
        constexpr bool is_constructible_with(std::index_sequence<idx...>, char) noexcept {
            return false;
        }

        template<class T, std::size_t n = sizeof(T) * 8, class = void>
        struct constructible_size {
            static_assert(n != 0, "T is not constructible");
            static constexpr std::size_t value = constructible_size<T, n - 1>::value;
        };

        template<class T, std::size_t n>
        struct constructible_size<T, n, std::enable_if_t<is_constructible_with<T>(std::make_index_sequence<n>(), false)>> {
            static constexpr std::size_t value = n;
        };
    } // namespace helper


    // tuple_likeな型Tの大きさを調べる
    template<class T, class = void>
    struct tuple_like_size {
        static constexpr std::size_t value = helper::constructible_size<T>::value;
    };

    template<class T>
    struct tuple_like_size<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        static constexpr std::size_t value = std::tuple_size_v<T>;
    };

    // tuple_likeな型Tの大きさを調べる
    template<class T>
    inline constexpr std::size_t tuple_like_size_v = tuple_like_size<T>::value;


    // tuple_likeなオブジェクトのidx(0 <= idx < 8)番目を求める関数クラス
    template<class T, class = void>
    struct GetFunction {
        #define GET(...) \
            { \
                auto&& [__VA_ARGS__] = std::forward<U>(tuple_like); \
                return std::get<idx> (std::forward_as_tuple(__VA_ARGS__)); \
            }

        template<std::size_t idx, class U>
        static constexpr decltype(auto) get(U&& tuple_like) noexcept {
            constexpr std::size_t size = tuple_like_size_v<T>;
            static_assert(size != 0, "The size must not be 0");
            static_assert(size < 9, "The size of tuple_like must be less than 9");
            if constexpr (size == 1) GET(a)
            else if constexpr (size == 2) GET(a, b)
            else if constexpr (size == 3) GET(a, b, c)
            else if constexpr (size == 4) GET(a, b, c, d)
            else if constexpr (size == 5) GET(a, b, c, d, e)
            else if constexpr (size == 6) GET(a, b, c, d, e, f)
            else if constexpr (size == 7) GET(a, b, c, d, e, f, g)
            else GET(a, b, c, d, e, f, g, h)
        }

        #undef GET
    };

    template<class T>
    struct GetFunction<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        template<std::size_t idx, class U>
        static constexpr decltype(auto) get(U&& tuple_like) noexcept {
            return std::get<idx>(std::forward<U>(tuple_like));
        }
    };

    namespace helper {
        template<std::size_t idx>
        struct GetHelper {
            template<class T>
            constexpr decltype(auto) operator ()(T&& tuple_like) const noexcept {
                return GetFunction<std::decay_t<T>>::template get<idx>(std::forward<T>(tuple_like));
            }
        };
    }

    // tuple-likeなオブジェクトのidx(0 <= idx < 8)番目を求める
    template<std::size_t idx>
    inline constexpr helper::GetHelper<idx> get;


    // tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
    template<std::size_t idx, class T>
    struct tuple_like_element {
        using type = std::decay_t<decltype(get<idx>(std::declval<T>()))>;
    };

    // tuple-likeな型Tのidx(0 <= idx < 8)番目の要素の型を調べる
    template<std::size_t idx, class T>
    using tuple_like_element_t = typename tuple_like_element<idx, T>::type;


    // 型Tがtuple_likeか調べる
    template<class T, class = void>
    struct is_tuple_like {
        static constexpr bool value = std::is_aggregate_v<T>;
    };

    template<class T>
    struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>::value)>> {
        static constexpr bool value = true;
    };

    // 型Tがtuple_likeか調べる
    template<class T>
    inline constexpr bool is_tuple_like_v = is_tuple_like<T>::value;
} // namespace kpr
#line 7 "kpr/meta/trait.hpp"

namespace kpr {
    namespace helper {
        template<class T>
        struct is_integer_helper {
            static constexpr bool value = std::is_integral_v<T>;
        };

        #ifdef __SIZEOF_INT128__
        template<>
        struct is_integer_helper<__int128_t> {
            static constexpr bool value = true;
        };
        template<>
        struct is_integer_helper<__uint128_t> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが整数か調べる

    template<class T>
    struct is_integer {
        static constexpr bool value = helper::is_integer_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが整数か調べる

    template<class T>
    inline constexpr bool is_integer_v = is_integer<T>::value;

    // 型Tが符号付き整数か調べる

    template<class T>
    struct is_signed_integer {
        static constexpr bool value = is_integer_v<T> && std::is_signed_v<T>;
    };
    // 型Tが符号付き整数か調べる

    template<class T>
    inline constexpr bool is_signed_integer_v = is_signed_integer<T>::value;

    // 型Tが符号無し整数か調べる

    template<class T>
    struct is_unsigned_integer {
        static constexpr bool value = is_integer_v<T> && !std::is_signed_v<T>;
    };
    // 型Tが符号無し整数か調べる

    template<class T>
    inline constexpr bool is_unsigned_integer_v = is_unsigned_integer<T>::value;

    namespace helper {
        template<class T>
        struct is_floating_point_helper {
            static constexpr bool value = std::is_floating_point_v<T>;
        };

        #ifdef __SIZEOF_FLOAT128__
        template<>
        struct is_floating_point_helper<__float128> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが浮動小数点数か調べる

    template<class T>
    struct is_floating_point {
        static constexpr bool value = helper::is_floating_point_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが浮動小数点数か調べる

    template<class T>
    inline constexpr bool is_floating_point_v = is_floating_point<T>::value;

    // 型Tが算術型か調べる

    template<class T>
    struct is_arithmetic {
        static constexpr bool value = is_integer_v<T> || is_floating_point_v<T>;
    };
    // 型Tが算術型か調べる

    template<class T>
    inline constexpr bool is_arithmetic_v = is_arithmetic<T>::value;

    // 型Tがスカラーか調べる

    template<class T>
    struct is_scalar {
        static constexpr bool value = is_arithmetic_v<T> || std::is_enum_v<T> || std::is_pointer_v<T> || std::is_member_pointer_v<T> || std::is_null_pointer_v<T>;
    };
    // 型Tがスカラーか調べる

    template<class T>
    inline constexpr bool is_scalar_v = is_scalar<T>::value;

    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    struct int_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The given integer type is too large");
            if constexpr (size <= 8) return std::int_least8_t{};
            else if constexpr (size <= 16) return std::int_least16_t{};
            else if constexpr (size <= 32) return std::int_least32_t{};
            else if constexpr (size <= 64) return std::int_least64_t{};
            else return __int128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    using int_least_t = typename int_least<size>::type;

    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    struct uint_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The give integer type is too large");
            if constexpr (size <= 8) return std::uint_least8_t{};
            else if constexpr (size <= 16) return std::uint_least16_t{};
            else if constexpr (size <= 32) return std::uint_least32_t{};
            else if constexpr (size <= 64) return std::uint_least64_t{};
            else return __uint128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    using uint_least_t = typename uint_least<size>::type;

    // Tの次に大きい整数型を調べる

    template<class T>
    struct next_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) <= 8, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 16>, uint_least_t<sizeof(T) * 16>>;
    };
    // Tの次に大きい整数型を調べる

    template<class T>
    using next_integer_t = typename next_integer<T>::type;

    // Tの次に小さい整数型を調べる

    template<class T>
    struct prev_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) >= 2, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 4>, uint_least_t<sizeof(T) * 4>>;
    };
    // Tの次に小さい整数型を調べる

    template<class T>
    using prev_integer_t = typename prev_integer<T>::type;

    // 型Tがイテレータか調べる

    template<class T, class = void>
    struct is_iterator {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>> {
        static constexpr bool value = true;
    };
    // 型Tがイテレータか調べる

    template<class T>
    inline constexpr bool is_iterator_v = is_iterator<T>::value;

    // 型TがRangeか調べる

    template<class T, class = void>
    struct is_range {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_range<T, std::void_t<decltype(std::begin(std::declval<std::add_lvalue_reference_t<T>>()), std::end(std::declval<std::add_lvalue_reference_t<T>>()))>> {
        static constexpr bool value = true;
    };
     // 型TがRangeか調べる

    template<class T>
    inline constexpr bool is_range_v = is_range<T>::value;

    // Range型Tからイテレータの型を調べる

    template<class T>
    struct range_iterator {
        using type = std::decay_t<decltype(std::begin(std::declval<T>()))>;
    };
    // Range型Tからイテレータの型を調べる

    template<class T>
    using range_iterator_t = typename range_iterator<T>::type;

    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    struct range_const_iterator {
        using type = std::decay_t<decltype(std::cbegin(std::declval<T>()))>;
    };
    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    using range_const_iterator_t = typename range_iterator<T>::type;

    // Range型Tから要素の型を調べる

    template<class T>
    struct range_value {
        using type = std::decay_t<decltype(*std::begin(std::declval<T>()))>;
    };
    // Range型Tから要素の型を調べる

    template<class T>
    using range_value_t = typename range_value<T>::type;
} // namespace kpr

#line 9 "kpr/algorithm/Hash.hpp"

namespace kpr {
    // ハッシュ(tuple_like, range対応)

    template<class, class = void>
    struct Hash;

    template<class T>
    struct Hash<T, std::enable_if_t<std::is_scalar_v<T>>> {
        using value_type = T;

        constexpr std::size_t operator ()(T a) const noexcept {
            return std::hash<T>{}(a);
        }
    };

    template<class T>
    struct Hash<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
        using value_type = T;

        template<std::size_t i = 0>
        constexpr std::size_t operator ()(const T& a) const noexcept {
            if constexpr (i == tuple_like_size_v<T>) return tuple_like_size_v<T>;
            else {
                std::size_t seed = operator()<i + 1>(a);
                return seed ^ (Hash<tuple_like_element_t<i, T>>{}(get<i>(a)) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4));
            }
        }
    };

    template<class T>
    struct Hash<T, std::enable_if_t<is_range_v<T>>>: Hash<range_value_t<T>> {
        using value_type = T;

        constexpr std::size_t operator ()(const T& a) const {
            std::size_t seed = std::size(a);
            for (auto&& i: a) seed ^= Hash<range_value_t<T>>{}(i) + 0x9e3779b97f4a7c15LU + (seed << 12) + (seed >> 4);
            return seed;
        }
    };
} // namespace kpr

#line 3 "kpr/meta/setting.hpp"

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 6 "kpr/function/monoid.hpp"

namespace kpr {
    // 足し算のmonoid

    template<class T>
    struct Add {
        using value_type = T;

        static constexpr T id() noexcept {
            return T{};
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a + b;
        }

        static constexpr T inv(const T& a) noexcept {
            return -a;
        }
    };

    // 掛け算のmonoid

    template<class T>
    struct Mul {
        using value_type = T;

        static constexpr T id() noexcept {
            return 1;
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a * b;
        }

        static constexpr T inv(const T& a) noexcept {
            return 1 / a;
        }
    };

    // minのmonoid

    template<class T>
    struct Min {
        using value_type = T;

        static constexpr T id() noexcept {
            if constexpr (std::numeric_limits<T>::has_infinity) return std::numeric_limits<T>::infinity();
            return std::numeric_limits<T>::max() / KYOPRO_INF_DIV;
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a < b ? a : b;
        }
    };

    // maxのmonoid

    template<class T>
    struct Max {
        using value_type = T;

        static constexpr T id() noexcept {
            if constexpr (std::numeric_limits<T>::has_infinity) return -std::numeric_limits<T>::infinity();
            if constexpr (std::is_signed_v<T>) return -(std::numeric_limits<T>::max() / KYOPRO_INF_DIV);
            return 0;
        }

        constexpr  T operator ()(const T& a, const T& b) const noexcept {
            return a > b ? a : b;
        }
    };


    // invを持つか調べる

    template<class, class = void>
    struct has_inv {
        static constexpr bool value = false;
    };

    template<class T>
    struct has_inv<T, std::void_t<decltype(&T::inv)>> {
        static constexpr bool value = true;
    };

    // invを持つか調べる

    template<class T>
    inline constexpr bool has_inv_v = has_inv<T>::value;
} // namespace kpr

#line 5 "kpr/math/power.hpp"

namespace kpr {
    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr T operator ()(T a, KYOPRO_BASE_UINT n, T init = Mul<T>::id()) const noexcept {
            while (n > 0) {
                if (n & 1) init *= a;
                a *= a;
                n >>= 1;
            }
            return init;
        }
    } power;
} // namespace kpr

#line 5 "kpr/meta/constant.hpp"

namespace kpr {
    // 問題で設定されたmod

    template<class T>
    inline constexpr T MOD = KYOPRO_DEFAULT_MOD;
    // 問題で設定されたmod

    inline constexpr KYOPRO_BASE_INT mod = MOD<KYOPRO_BASE_INT>;

    // 無限大を表す整数

    template<class T>
    inline constexpr T INF = std::numeric_limits<T>::max() / KYOPRO_INF_DIV;
    // 無限大を表す整数

    inline constexpr KYOPRO_BASE_INT inf = INF<KYOPRO_BASE_INT>;

    // 許容される小数誤差

    template<class T, KYOPRO_BASE_UINT decimal_precision = KYOPRO_DECIMAL_PRECISION>
    inline constexpr KYOPRO_BASE_FLOAT EPS = static_cast<T>(1) / power(10ULL, decimal_precision);
    // 許容される小数誤差

    inline constexpr KYOPRO_BASE_FLOAT eps = EPS<KYOPRO_BASE_FLOAT>;

    // 円周率

    template<class T>
    inline constexpr T PI = 3.14159265358979323846;
    // 円周率

    inline constexpr KYOPRO_BASE_FLOAT pi = PI<KYOPRO_BASE_FLOAT>;
} // namespace kpr

#line 2 "kpr/io/in.hpp"
#include <unistd.h>
#include <array>
#include <bitset>
#line 7 "kpr/io/in.hpp"
#include <cstdio>
#include <string>
#line 5 "kpr/io/io_option.hpp"

namespace kpr {
    template<class Tuple, std::size_t idx>
    struct Indexed {
        Tuple args_tuple;
        template<class... Args>
        constexpr Indexed(Args&&... args) noexcept: args_tuple{std::forward<Args>(args)...} {}
    };

    template<std::size_t i, class... Args>
    constexpr auto indexed(Args&&... args) noexcept {
        return Indexed<std::tuple<Args...>, i>{std::forward<Args>(args)...};
    }

    template<class... Args>
    constexpr auto idx1(Args&&... args) noexcept {
        return indexed<1>(std::forward<Args>(args)...);
    }

    template<class Tuple, bool... seps>
    struct SepWith {
        Tuple args_tuple;
        template<class... Args>
        constexpr SepWith(Args&&... args) noexcept: args_tuple{std::forward<Args>(args)...} {}
    };

    template<bool... seps, class... Args>
    constexpr auto sep_with(Args&&... args) noexcept {
        return SepWith<std::tuple<Args...>, seps...>{std::forward<Args>(args)...};
    }
} // namespace kpr

#line 16 "kpr/io/in.hpp"

namespace kpr {
    // バッファを用いてファイルを読み込むクラス

    template<std::size_t buf_size = KYOPRO_BUFFER_SIZE>
    struct Reader {
    private:
        int fd, idx;
        std::array<char, buf_size> buffer;

    public:
        // バッファサイズを取得

        static constexpr KYOPRO_BASE_INT get_buf_size() noexcept {
            return buf_size;
        }

        Reader() {
            [[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
        }
        Reader(int fd): fd(fd), idx(0), buffer() {
            [[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
        }
        Reader(FILE* fp): fd(fileno(fp)), idx(0), buffer() {
            [[maybe_unused]] ssize_t res = read(fd, buffer.begin(), buf_size);
        }

        // 入力イテレータ

        struct iterator {
        private:
            Reader& reader;

        public:
            using difference_type = void;
            using value_type = void;
            using pointer = void;
            using reference = void;
            using iterator_category = std::input_iterator_tag;

            iterator() noexcept = default;
            iterator(Reader& reader) noexcept: reader(reader) {}

            iterator& operator ++() {
                ++reader.idx;
                if (reader.idx == buf_size) {
                    [[maybe_unused]] ssize_t res = read(reader.fd, reader.buffer.begin(), buf_size);
                    reader.idx = 0;
                }
                return *this;
            }

            iterator operator ++(int) {
                iterator before = *this;
                operator ++();
                return before;
            }

            char& operator *() const {
                return reader.buffer[reader.idx];
            }
        };

        // ファイルの最初を示すイテレータを取得

        iterator begin() noexcept {
            return iterator(*this);
        }
    };

    // 標準入力

    Reader input{0};


    // 値の入力の関数クラス

    template<class, class = void>
    struct ScanFunction;

    // 入力イテレータを用いて値を入力するクラス

    template<class Iterator, std::size_t decimal_precision = KYOPRO_DECIMAL_PRECISION>
    struct Scanner {
        using iterator_type = Iterator;

        // 入力イテレータ

        Iterator itr;

        // 指定された小数誤差を取得

        static constexpr KYOPRO_BASE_INT get_decimal_precision() noexcept {
            return decimal_precision;
        }

        Scanner() noexcept = default;
        Scanner(Iterator itr) noexcept: itr(itr) {}

        // 次の文字までの空白を無視する

        void discard_space() {
            while (('\t' <= *itr && *itr <= '\r') || *itr == ' ') ++itr;
        }

        // 整数、小数を入力

        template<class T>
        void scan_arithmetic(T& a) {
            discard_space();
            bool sgn = false;
            if constexpr (!std::is_unsigned_v<T>) if (*itr == '-') {
                sgn = true;
                ++itr;
            }
            a = 0;
            for (; '0' <= *itr && *itr <= '9'; ++itr) a = a * 10 + *itr - '0';
            if (*itr == '.') {
                ++itr;
                if constexpr (is_floating_point_v<T>) {
                    constexpr std::uint_fast64_t power_decimal_precision = power(10ULL, decimal_precision);
                    T d = 0;
                    std::uint_fast64_t i = 1;
                    for (; '0' <= *itr && *itr <= '9' && i < power_decimal_precision; i *= 10) {
                        d = d * 10 + *itr - '0';
                        ++itr;
                    }
                    a += d / i;
                }
                while ('0' <= *itr && *itr <= '9') ++itr;
            }
            if constexpr (!std::is_unsigned_v<T>) if (sgn) a = -a;
        }

        // 複数の値を入力

        void operator ()() {}
        template<class Head, class... Args>
        void operator ()(Head&& head, Args&&... args) {
            ScanFunction<std::decay_t<Head>>::scan(*this, std::forward<Head>(head));
            operator ()(std::forward<Args>(args)...);
        }
    };

    template<>
    struct ScanFunction<char> {
        template<class Scanner>
        static void scan(Scanner& scanner, char& a) {
            scanner.discard_space();
            a = *scanner.itr;
            ++scanner.itr;
        }
    };

    template<>
    struct ScanFunction<bool> {
        template<class Scanner>
        static void scan(Scanner& scanner, bool& a) {
            scanner.discard_space();
            a = *scanner.itr != '0';
        }
    };

    template<>
    struct ScanFunction<std::string> {
        template<class Scanner>
        static void scan(Scanner& scanner, std::string& a) {
            scanner.discard_space();
            a.clear();
            while ((*scanner.itr < '\t' || '\r' < *scanner.itr) && *scanner.itr != ' ') {
                a += *scanner.itr;
                ++scanner.itr;
            }
        }
    };

    template<std::size_t len>
    struct ScanFunction<std::bitset<len>> {
        template<class Scanner>
        static void scan(Scanner& scanner, std::bitset<len>& a) {
            scanner.discard_space();
            for (int i = len - 1; i >= 0; ++i) {
                a[i] = *scanner.itr != '0';
                ++scanner.itr;
            }
        }
    };

    template<class T>
    struct ScanFunction<T, std::enable_if_t<is_arithmetic_v<T>>> {
        template<class Scanner>
        static void scan(Scanner& scanner, T& a) {
            scanner.scan_arithmetic(a);
        }
    };

    template<class T>
    struct ScanFunction<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
        template<std::size_t i = 0, class Scanner>
        static void scan(Scanner& scanner, T& a) {
            if constexpr (i < tuple_like_size_v<T>) {
                ScanFunction<std::decay_t<tuple_like_element_t<i, T>>>::scan(scanner, get<i>(a));
                scan<i + 1>(scanner, a);
            }
        }
    };

    template<class T>
    struct ScanFunction<T, std::enable_if_t<is_range_v<T>>> {
        template<class Scanner>
        static void scan(Scanner& scanner, T& a) {
            for (auto&& i: a) ScanFunction<range_value_t<T>>::scan(scanner, i);
        }
    };

    template<class Tuple, std::size_t idx>
    struct ScanFunction<Indexed<Tuple, idx>> {
        template<class Scanner>
        struct ScannerWrapper: Scanner {
            template<class T>
            void scan_arithmetic(T& a) {
                Scanner::scan_arithmetic(a);
                --a;
            }
        };
        template<std::size_t i = 0, class Scanner>
        static void scan_impl(ScannerWrapper<Scanner>& scanner_wrapper, const Tuple& args_tuple) {
            if constexpr (i < tuple_like_size_v<Tuple>) {
                ScanFunction<std::decay_t<tuple_like_element_t<i, Tuple>>>::scan(scanner_wrapper, get<i>(args_tuple));
                scan_impl<i + 1>(scanner_wrapper, args_tuple);
            }
        }
        template<class Scanner>
        static void scan(Scanner& scanner, const Indexed<Tuple, idx>& a) {
            ScannerWrapper<Scanner>& scanner_wrapper = static_cast<ScannerWrapper<Scanner>&>(scanner);
            scan_impl(scanner_wrapper, a.args_tuple);
        }
    };

    // 標準入力から値を入力する関数

    Scanner<Reader<>::iterator> scan{input.begin()};
} // namespace kpr

#line 3 "kpr/io/out.hpp"
#include <algorithm>
#line 6 "kpr/io/out.hpp"
#include <cmath>
#line 11 "kpr/io/out.hpp"
#include <string_view>
#line 19 "kpr/io/out.hpp"

namespace kpr {
    // バッファを用いてファイルに書き込むクラス

    template<std::size_t buf_size = KYOPRO_BUFFER_SIZE>
    struct Writer {
    private:
        int fd, idx;
        std::array<char, buf_size> buffer;

    public:
        // バッファサイズを取得

        static constexpr KYOPRO_BASE_INT get_buf_size() noexcept {
            return buf_size;
        }

        Writer() noexcept = default;
        Writer(int fd) noexcept: fd(fd), idx(0), buffer() {}
        Writer(FILE* fp) noexcept: fd(fileno(fp)), idx(0), buffer() {}

        ~Writer() {
            [[maybe_unused]]ssize_t res = write(fd, buffer.begin(), idx);
        }

        // 出力イテレータ

        struct iterator {
        private:
            Writer& writer;

        public:
            using difference_type = void;
            using value_type = void;
            using pointer = void;
            using reference = void;
            using iterator_category = std::output_iterator_tag;

            iterator() noexcept = default;
            iterator(Writer& writer) noexcept: writer(writer) {}

            iterator& operator ++() {
                ++writer.idx;
                if (writer.idx == buf_size) {
                [[maybe_unused]]ssize_t res = write(writer.fd, writer.buffer.begin(), buf_size);
                writer.idx = 0;
                }
                return *this;
            }

            iterator operator ++(int) {
                iterator before = *this;
                operator ++();
                return before;
            }

            char& operator *() const {
                return writer.buffer[writer.idx];
            }

            // バッファを全て出力する

            void flush() const {
                [[maybe_unused]] ssize_t res = write(writer.fd, writer.buffer.begin(), writer.idx);
            }
        };

        // ファイルの最初を示すイテレータを取得

        iterator begin() noexcept {
            return iterator(*this);
        }
    };

    // 標準出力、標準エラー出力

    Writer output{1}, error{2};

    // 値の出力の関数クラス

    template<class, class = void>
    struct PrintFunction;

    // 出力イテレータを用いて値を出力するクラス

    template<class Iterator, bool _space = true, bool _line = true, bool _debug = false, bool _comment = false, bool _flush = false, std::size_t decimal_precision = KYOPRO_DECIMAL_PRECISION>
    struct Printer {
        using iterator_type = Iterator;

        // 指定されたオプション

        static constexpr bool space = _space, line = _line, debug = _debug, comment = _comment, flush = _flush;

        // 指定された小数誤差を取得

        static constexpr KYOPRO_BASE_INT get_decimal_precision() noexcept {
            return decimal_precision;
        }

        // 出力イテレータ

        Iterator itr;

        Printer() noexcept = default;
        Printer(Iterator itr) noexcept: itr(itr) {}

        // 一文字出力する

        void print_char(char c) {
            *itr = c;
            ++itr;
        }

        // 整数、小数を出力

        template<class T>
        void print_arithmetic(T a) {
            if constexpr (is_floating_point_v<T>) {
                if (a == std::numeric_limits<T>::infinity()) {
                    print_char('i');
                    print_char('n');
                    print_char('f');
                    return;
                }
                if (a == -std::numeric_limits<T>::infinity()) {
                    print_char('-');
                    print_char('i');
                    print_char('n');
                    print_char('f');
                    return;
                }
                if (std::isnan(a)) {
                    print_char('n');
                    print_char('a');
                    print_char('n');
                    return;
                }
            }
            if constexpr (std::is_signed_v<T>) if (a < 0) {
                print_char('-');
                a = -a;
            }
            std::uint_fast64_t p = a;
            std::string s;
            do {
                s += '0' + p % 10;
                p /= 10;
            } while (p > 0);
            for (auto i = s.rbegin(); i != s.rend(); ++i) print_char(*i);
            if constexpr (is_integer_v<T>) return;
            print_char('.');
            a -= p;
            for (int i = 0; i < static_cast<int>(decimal_precision); ++i) {
                a *= 10;
                print_char('0' + static_cast<std::uint_fast64_t>(a) % 10);
            }
        }

        // 区切り文字を出力する

        void print_sep() {
            if constexpr (debug) print_char(',');
            if constexpr (space) print_char(' ');
        }

        // 区切り文字を出力する(型によって変更)

        template<class type>
        void print_sep_by_type() {
            if constexpr (is_tuple_like_v<type> || is_range_v<type>) {
                print_end();
                if constexpr (comment) print_comment();
            } else print_sep();
        }

        // 最後の文字を出力する

        void print_end() {
            if constexpr (debug) print_char(',');
            if constexpr (line) print_char('\n');
        }

        // コメント記号を出力する

        void print_comment() {
            if constexpr (comment) {
                print_char('#');
                print_char(' ');
            }
        }

        // 複数の値を出力

        template<bool first = true>
        void operator ()() {
            if constexpr (first) print_comment();
            print_end();
            if constexpr (flush) itr.flush();
        }
        template<bool first = true, class Head, class... Args>
        void operator ()(Head&& head, Args&&... args) {
            if constexpr (first) print_comment();
            else print_sep();
            PrintFunction<std::decay_t<Head>>::print(*this, std::forward<Head>(head));
            operator ()<false>(std::forward<Args>(args)...);
        }
    };

    template<>
    struct PrintFunction<char> {
        template<class Printer>
        static void print(Printer& printer, char a) {
            if constexpr (Printer::debug) printer.print_char('\'');
            printer.print_char(a);
            if constexpr (Printer::debug) printer.print_char('\'');
        }
    };

    template<>
    struct PrintFunction<bool> {
        template<class Printer>
        static void print(Printer& printer, bool a) {
            printer.print_char(static_cast<char>('0' + a));
        }
    };

    template<class T>
    struct PrintFunction<T, std::enable_if_t<std::is_convertible_v<T, std::string_view>>> {
        template<class Printer>
        static void print(Printer& printer, std::string_view a) {
            if constexpr (Printer::debug) printer.print_char('"');
            for (char i: a) printer.print_char(i);
            if constexpr (Printer::debug) printer.print_char('"');
        }
    };

    template<std::size_t len>
    struct PrintFunction<std::bitset<len>> {
        template<class Printer>
        static void print(Printer& printer, const std::bitset<len>& a) {
            for (int i = len - 1; i >= 0; --i) PrintFunction<bool>::print(printer, a[i]);
        }
    };

    template<class T>
    struct PrintFunction<T, std::enable_if_t<std::is_arithmetic_v<T>>> {
        template<class Printer>
        static void print(Printer& printer, T a) {
            printer.print_arithmetic(a);
        }
    };

    template<class T>
    struct PrintFunction<T, std::enable_if_t<is_tuple_like_v<T> && !is_range_v<T>>> {
        template<std::size_t i = 0, class Printer>
        static void print(Printer& printer, const T& a) {
            using element_type = std::decay_t<tuple_like_element_t<i, T>>;
            if constexpr (Printer::debug && i == 0) printer.print_char('{');
            if constexpr (tuple_like_size_v<T> != 0) PrintFunction<element_type>::print(printer, get<i>(a));
            if constexpr (i + 1 < tuple_like_size_v<T>) {
                printer.template print_sep_by_type<element_type>();
                print<i + 1>(printer, a);
            } else if constexpr (Printer::debug) printer.print_char('}');
        }
    };

    template<class T>
    struct PrintFunction<T, std::enable_if_t<is_range_v<T> && !std::is_convertible_v<T, std::string_view>>> {
        template<class Printer>
        static void print(Printer& printer, const T& a) {
            using value_type = range_value_t<T>;
            if constexpr (Printer::debug) printer.print_char('{');
            if (!std::empty(a)) {
                for (auto i = std::begin(a); ; ) {
                    PrintFunction<value_type>::print(printer, *i);
                    if (++i != std::end(a)) printer.template print_sep_by_type<value_type>();
                    else break;
                }
            }
            if constexpr (Printer::debug) printer.print_char('}');
        }
    };

    template<class Tuple, std::size_t idx>
    struct PrintFunction<Indexed<Tuple, idx>> {
        template<class Printer>
        struct PrinterWrapper: Printer {
            template<class T>
            void print_arithmetic(T a) {
                Printer::print_arithmetic(a + 1);
            }
        };
        template<class Printer>
        static void print(Printer& printer, const Indexed<Tuple, idx>& a) {
            PrinterWrapper<Printer>& printer_wrapper = static_cast<PrinterWrapper<Printer>&>(printer);
            PrintFunction<Tuple>::print(printer_wrapper, a.args_tuple);
        }
    };

    // 標準出力、標準エラー出力に値を出力する(改行、区切り文字なし)

    Printer<Writer<>::iterator, false, false> print{output.begin()}, eprint{error.begin()};
    // 標準出力、標準エラー出力に値を出力する(改行、区切り文字あり)

    Printer<Writer<>::iterator> println{output.begin()}, eprintln{error.begin()};
} // namespace kpr

#line 6 "kpr/math/Montgomery.hpp"

namespace kpr {
    template<class T>
    struct Montgomery {
        static_assert(is_unsigned_integer_v<T>, "The given type must be an unsigned integer type");

        using value_type = T;

        T mod;

    private:
        using larger_type = next_integer_t<T>;

        T r, n2;

    public:
        constexpr void set_mod(T mod) noexcept {
            this->mod = mod;
            n2 = -static_cast<larger_type>(mod) % mod;
            T t = 0;
            r = 0;
            for (int i = 0; i < std::numeric_limits<T>::digits; ++i) {
                if (!(t & 1)) {
                    t += mod;
                    r += static_cast<T>(1) << static_cast<T>(i);
                }
                t >>= 1;
            }
        }

        constexpr KYOPRO_BASE_INT get_mod() const noexcept {
            return mod;
        }

        Montgomery() noexcept = default;
        Montgomery(T mod) noexcept {
            set_mod(mod);
        }

        constexpr T transform(T x) const noexcept {
            return reduce(static_cast<larger_type>(x) * n2);
        }

        constexpr T inv_transform(T x) const noexcept {
            T y = reduce(x);
            return y >= mod ? y - mod : y;
        }

        constexpr T reduce(larger_type x) const noexcept {
            return (x + static_cast<larger_type>(static_cast<T>(x) * r) * mod) >> std::numeric_limits<T>::digits;
        }
    };
} // namespace kpr

#line 13 "kpr/math/DynamicModInt.hpp"

namespace kpr {
    template<class T, std::size_t kind = 0, bool = false>
    struct DynamicModInt {
        static_assert(std::is_unsigned_v<T>, "The given type must be an unsigned integer type");

        using value_type = T;

    private:
        using larger_type = next_integer_t<T>;

        inline static Montgomery<T> montgomery;

    public:
        T value;

        static constexpr KYOPRO_BASE_INT get_kind() noexcept {
            return kind;
        }

        static void set_mod(T mod) noexcept {
            montgomery.set_mod(mod);
        }

        static KYOPRO_BASE_INT get_mod() noexcept {
            return montgomery.mod;
        }

        KYOPRO_BASE_INT get_val() noexcept {
            return montgomery.inv_transform(value);
        }

        DynamicModInt() noexcept = default;
        DynamicModInt(T value) noexcept: value(montgomery.transform(value % montgomery.mod + montgomery.mod)) {}

        template<class U>
        explicit operator U() const noexcept {
            return montgomery.inv_transform(value);
        }

        static DynamicModInt raw(T value) noexcept {
            DynamicModInt res;
            res.value = montgomery.transform(value);
            return res;
        }

        DynamicModInt pow(KYOPRO_BASE_UINT n) const noexcept {
            DynamicModInt res = 1, a = *this;
            while (n > 0) {
                if (n & 1) res = res * a;
                a = a * a;
                n >>= 1;
            }
            return res;
        }

        DynamicModInt inv() const noexcept {
            return pow(montgomery.mod - 2);
        }

        DynamicModInt operator +() const noexcept {
            return *this;
        }

        DynamicModInt operator -() const noexcept {
            return value == 0 ? 0 : montgomery.mod - value;
        }

        DynamicModInt& operator ++() noexcept {
            *this += DynamicModInt::raw(1);
            return *this;
        }

        DynamicModInt operator ++(int) noexcept {
            DynamicModInt before = *this;
            ++*this;
            return before;
        }

        DynamicModInt& operator --() noexcept {
            *this -= DynamicModInt::raw(1);
            return *this;
        }

        DynamicModInt operator --(int) noexcept {
            DynamicModInt before = *this;
            --*this;
            return before;
        }

        DynamicModInt& operator +=(DynamicModInt rhs) noexcept {
            if ((value += rhs.value - (montgomery.mod << 1)) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
            return *this;
        }

        DynamicModInt& operator -=(DynamicModInt rhs) noexcept {
            if ((value -= rhs.value) > std::numeric_limits<std::make_signed_t<T>>::max()) value += montgomery.mod << 1;
            return *this;
        }

        DynamicModInt& operator *=(DynamicModInt rhs) noexcept {
            value = montgomery.reduce(static_cast<larger_type>(value) * rhs.value);
            return *this;
        }

        DynamicModInt& operator /=(DynamicModInt rhs) noexcept {
            value = montgomery.reduce(static_cast<larger_type>(value) * rhs.inv().value);
            return *this;
        }

        friend DynamicModInt operator +(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs += rhs;
        }

        friend DynamicModInt operator -(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs -= rhs;
        }

        friend DynamicModInt operator *(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs *= rhs;
        }

        friend DynamicModInt operator /(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs /= rhs;
        }

        friend bool operator ==(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs.value == rhs.value;
        }

        friend bool operator !=(DynamicModInt lhs, DynamicModInt rhs) noexcept {
            return lhs.value != rhs.value;
        }

        friend struct ScanFunction<DynamicModInt>;

        friend struct PrintFunction<DynamicModInt>;
    };

    template<class T, std::size_t kind>
    struct ScanFunction<DynamicModInt<T, kind>> {
        template<class Scanner>
        static void scan(Scanner& scanner, DynamicModInt<T, kind>& a) {
            std::int_fast64_t value;
            ScanFunction<std::int_fast64_t>::scan(scanner, value);
            a.value = a.montgomery.transform(value % a.montgomery.mod + a.montgomery.mod);
        }
    };

    template<class T, std::size_t kind>
    struct PrintFunction<DynamicModInt<T, kind>> {
        template<class Printer>
        static void print(Printer& printer, const DynamicModInt<T, kind>& a) {
            PrintFunction<T>::print(printer, a.montgomery.inv_transform(a.value));
        }
    };

    template<class T, std::size_t kind>
    struct Hash<DynamicModInt<T, kind>> {
        using value_type = DynamicModInt<T, kind>;

        std::size_t operator ()(DynamicModInt<T, kind> a) const noexcept {
            return static_cast<std::size_t>(a);
        }
    };
} // namespace kpr