This documentation is automatically generated by online-judge-tools/verification-helper
#include "mod/dynamic_modint_64.hpp"
#pragma once
#include "mod/modint_common.hpp"
#include "mod/barrett.hpp"
// https://codeforces.com/contest/453/problem/D
template <int id>
struct Dynamic_Modint_64 {
static constexpr bool is_modint = true;
using mint = Dynamic_Modint_64;
u64 val;
static Barrett_64 bt;
static u64 umod() { return bt.umod(); }
static ll get_mod() { return (ll)(bt.umod()); }
static void set_mod(ll m) {
assert(1 <= m);
bt = Barrett_64(m);
}
Dynamic_Modint_64() : val(0) {}
Dynamic_Modint_64(u64 x) : val(bt.modulo(x)) {}
Dynamic_Modint_64(u128 x) : val(bt.modulo(x)) {}
Dynamic_Modint_64(int x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
Dynamic_Modint_64(ll x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
Dynamic_Modint_64(i128 x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
mint& operator+=(const mint& rhs) {
val = (val += rhs.val) < umod() ? val : val - umod();
return *this;
}
mint& operator-=(const mint& rhs) {
val = (val += umod() - rhs.val) < umod() ? val : val - umod();
return *this;
}
mint& operator*=(const mint& rhs) {
val = bt.mul(val, rhs.val);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inverse(); }
mint operator-() const { return mint() - *this; }
mint pow(ll n) const {
assert(0 <= n);
mint x = *this, r = u64(1);
while (n) {
if (n & 1) r *= x;
x *= x, n >>= 1;
}
return r;
}
mint inverse() const {
ll x = val, mod = get_mod();
ll a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
if (u < 0) u += mod;
return u64(u);
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs.val == rhs.val;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs.val != rhs.val;
}
};
#ifdef FASTIO
template <int id>
void rd(Dynamic_Modint_64<id>& x) {
fastio::rd(x.val);
assert(0 <= x.val && x.val < Dynamic_Modint_64<id>::get_mod());
}
template <int id>
void wt(Dynamic_Modint_64<id> x) {
fastio::wt(x.val);
}
#endif
using dmint64 = Dynamic_Modint_64<-1>;
template <int id>
Barrett_64 Dynamic_Modint_64<id>::bt;
#line 2 "mod/dynamic_modint_64.hpp"
#line 2 "mod/modint_common.hpp"
struct has_mod_impl {
template <class T>
static auto check(T &&x) -> decltype(x.get_mod(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_mod : public decltype(has_mod_impl::check<T>(std::declval<T>())) {};
template <typename mint>
mint inv(int n) {
static const int mod = mint::get_mod();
static vector<mint> dat = {0, 1};
assert(0 <= n);
if (n >= mod) n %= mod;
while (len(dat) <= n) {
int k = len(dat);
int q = (mod + k - 1) / k;
dat.eb(dat[k * q - mod] * mint::raw(q));
}
return dat[n];
}
template <typename mint>
mint fact(int n) {
static const int mod = mint::get_mod();
assert(0 <= n && n < mod);
static vector<mint> dat = {1, 1};
while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * mint::raw(len(dat)));
return dat[n];
}
template <typename mint>
mint fact_inv(int n) {
static vector<mint> dat = {1, 1};
if (n < 0) return mint(0);
while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * inv<mint>(len(dat)));
return dat[n];
}
template <class mint, class... Ts>
mint fact_invs(Ts... xs) {
return (mint(1) * ... * fact_inv<mint>(xs));
}
template <typename mint, class Head, class... Tail>
mint multinomial(Head &&head, Tail &&... tail) {
return fact<mint>(head) * fact_invs<mint>(std::forward<Tail>(tail)...);
}
template <typename mint>
mint C_dense(int n, int k) {
static vvc<mint> C;
static int H = 0, W = 0;
auto calc = [&](int i, int j) -> mint {
if (i == 0) return (j == 0 ? mint(1) : mint(0));
return C[i - 1][j] + (j ? C[i - 1][j - 1] : 0);
};
if (W <= k) {
FOR(i, H) {
C[i].resize(k + 1);
FOR(j, W, k + 1) { C[i][j] = calc(i, j); }
}
W = k + 1;
}
if (H <= n) {
C.resize(n + 1);
FOR(i, H, n + 1) {
C[i].resize(W);
FOR(j, W) { C[i][j] = calc(i, j); }
}
H = n + 1;
}
return C[n][k];
}
template <typename mint, bool large = false, bool dense = false>
mint C(ll n, ll k) {
assert(n >= 0);
if (k < 0 || n < k) return 0;
if constexpr (dense) return C_dense<mint>(n, k);
if constexpr (!large) return multinomial<mint>(n, k, n - k);
k = min(k, n - k);
mint x(1);
FOR(i, k) x *= mint(n - i);
return x * fact_inv<mint>(k);
}
template <typename mint, bool large = false>
mint C_inv(ll n, ll k) {
assert(n >= 0);
assert(0 <= k && k <= n);
if (!large) return fact_inv<mint>(n) * fact<mint>(k) * fact<mint>(n - k);
return mint(1) / C<mint, 1>(n, k);
}
// [x^d](1-x)^{-n}
template <typename mint, bool large = false, bool dense = false>
mint C_negative(ll n, ll d) {
assert(n >= 0);
if (d < 0) return mint(0);
if (n == 0) { return (d == 0 ? mint(1) : mint(0)); }
return C<mint, large, dense>(n + d - 1, d);
}
#line 2 "mod/barrett.hpp"
// https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
struct Barrett {
u32 m;
u64 im;
explicit Barrett(u32 m = 1) : m(m), im(u64(-1) / m + 1) {}
u32 umod() const { return m; }
u32 modulo(u64 z) {
if (m == 1) return 0;
u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
u64 y = x * m;
return (z - y + (z < y ? m : 0));
}
u64 floor(u64 z) {
if (m == 1) return z;
u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
u64 y = x * m;
return (z < y ? x - 1 : x);
}
pair<u64, u32> divmod(u64 z) {
if (m == 1) return {z, 0};
u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
u64 y = x * m;
if (z < y) return {x - 1, z - y + m};
return {x, z - y};
}
u32 mul(u32 a, u32 b) { return modulo(u64(a) * b); }
};
struct Barrett_64 {
u128 mod, mh, ml;
explicit Barrett_64(u64 mod = 1) : mod(mod) {
u128 m = u128(-1) / mod;
if (m * mod + mod == u128(0)) ++m;
mh = m >> 64;
ml = m & u64(-1);
}
u64 umod() const { return mod; }
u64 modulo(u128 x) {
u128 z = (x & u64(-1)) * ml;
z = (x & u64(-1)) * mh + (x >> 64) * ml + (z >> 64);
z = (x >> 64) * mh + (z >> 64);
x -= z * mod;
return x < mod ? x : x - mod;
}
u64 mul(u64 a, u64 b) { return modulo(u128(a) * b); }
};
#line 5 "mod/dynamic_modint_64.hpp"
// https://codeforces.com/contest/453/problem/D
template <int id>
struct Dynamic_Modint_64 {
static constexpr bool is_modint = true;
using mint = Dynamic_Modint_64;
u64 val;
static Barrett_64 bt;
static u64 umod() { return bt.umod(); }
static ll get_mod() { return (ll)(bt.umod()); }
static void set_mod(ll m) {
assert(1 <= m);
bt = Barrett_64(m);
}
Dynamic_Modint_64() : val(0) {}
Dynamic_Modint_64(u64 x) : val(bt.modulo(x)) {}
Dynamic_Modint_64(u128 x) : val(bt.modulo(x)) {}
Dynamic_Modint_64(int x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
Dynamic_Modint_64(ll x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
Dynamic_Modint_64(i128 x) : val((x %= get_mod()) < 0 ? x + get_mod() : x) {}
mint& operator+=(const mint& rhs) {
val = (val += rhs.val) < umod() ? val : val - umod();
return *this;
}
mint& operator-=(const mint& rhs) {
val = (val += umod() - rhs.val) < umod() ? val : val - umod();
return *this;
}
mint& operator*=(const mint& rhs) {
val = bt.mul(val, rhs.val);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inverse(); }
mint operator-() const { return mint() - *this; }
mint pow(ll n) const {
assert(0 <= n);
mint x = *this, r = u64(1);
while (n) {
if (n & 1) r *= x;
x *= x, n >>= 1;
}
return r;
}
mint inverse() const {
ll x = val, mod = get_mod();
ll a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
if (u < 0) u += mod;
return u64(u);
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs.val == rhs.val;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs.val != rhs.val;
}
};
#ifdef FASTIO
template <int id>
void rd(Dynamic_Modint_64<id>& x) {
fastio::rd(x.val);
assert(0 <= x.val && x.val < Dynamic_Modint_64<id>::get_mod());
}
template <int id>
void wt(Dynamic_Modint_64<id> x) {
fastio::wt(x.val);
}
#endif
using dmint64 = Dynamic_Modint_64<-1>;
template <int id>
Barrett_64 Dynamic_Modint_64<id>::bt;