#include #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_FORMAL_POWER_SERIES_HPP #define KOTONE_FORMAL_POWER_SERIES_HPP 1 #include #include #include #include // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_INTERNAL_TYPE_TRAITS_HPP #define KOTONE_INTERNAL_TYPE_TRAITS_HPP 1 #include namespace kotone { template concept number = std::is_arithmetic_v; template concept signed_number = std::signed_integral || std::floating_point; template concept compatible_modint = requires(mint a, mint b, int64_t x) { { mint::mod() } -> std::convertible_to; mint{}; mint{1}; mint{x}; { a + b } -> std::same_as; { a - b } -> std::same_as; { -a } -> std::same_as; { a * b } -> std::same_as; { a / b } -> std::same_as; { a.inv() } -> std::same_as; { a.pow(x) } -> std::same_as; { a += b } -> std::same_as; { a -= b } -> std::same_as; { a *= b } -> std::same_as; { a /= b } -> std::same_as; { a == b } -> std::convertible_to; { a != b } -> std::convertible_to; { a.val() } -> std::convertible_to; }; template concept additive = requires(T a, T b) { T{}; { a + b } -> std::same_as; { a - b } -> std::same_as; { -a } -> std::same_as; { a == b } -> std::convertible_to; { a != b } -> std::convertible_to; }; template concept mutable_additive = ( additive && requires(T a, T b) { { a += b } -> std::same_as; { a -= b } -> std::same_as; { ++a } -> std::same_as; { --a } -> std::same_as; { a++ } -> std::same_as; { a-- } -> std::same_as; } ); } // namespace kotone #endif // KOTONE_INTERNAL_TYPE_TRAITS namespace kotone { // A formal power series (`fps`) inherited from `vector` that supports various operations. template struct formal_power_series : std::vector { using fps = formal_power_series; using std::vector::vector; using std::vector::operator=; // Adds `other` to `*this`. fps& operator+=(const fps &other) { if (this->size() < other.size()) this->resize(other.size()); for (std::size_t i = 0; i < other.size(); i++) (*this)[i] += other[i]; return *this; } // Subtracts `other` from `*this`. fps& operator-=(const fps &other) { if (this->size() < other.size()) this->resize(other.size()); for (std::size_t i = 0; i < other.size(); i++) (*this)[i] -= other[i]; return *this; } // Multiplies `*this` by `other`. fps& operator*=(const fps &other) { if (this->empty() || other.empty()) this->clear(); else if constexpr (using_ntt) *this = atcoder::convolution(*this, other); else { fps result(this->size() + other.size() - 1); for (std::size_t i = 0; i < this->size(); i++) { for (std::size_t j = 0; j < other.size(); j++) { result[i + j] += (*this)[i] * other[j]; } } *this = result; } return *this; } // Multiplies each coefficient by `m`. fps& operator*=(const mint &m) { for (mint &c : *this) c *= m; return *this; } // Divides each coefficient by `m`. // Requires `m != 0`. fps& operator/=(const mint &m) { assert(m != 0); for (mint &c : *this) c /= m; return *this; } // Returns a copy of `*this`. fps operator+() const { return *this; } // Returns a copy of negated `*this`. fps operator-() const { return fps{} - *this; } // Returns `*this` evaluated at `m`. mint operator()(const mint &m) const { mint result = 0; for (std::size_t i = this->size(); i--;) { result *= m; result += (*this)[i]; } return result; } // Strips trailing `0`'s. void strip() { while (this->size() && this->back() == 0) this->pop_back(); } // Divides `*this` by `other` and assigns the quotient to `*this`. // Requires `other` to contain nonzero coefficients. fps& operator/=(const fps &other) { fps denom(other.begin(), other.end()); denom.strip(); assert(!denom.empty()); fps num(this->begin(), this->end()); num.strip(); int n = num.size(), m = denom.size(); if (n < m) { this->clear(); return *this; } std::reverse(denom.begin(), denom.end()); std::reverse(num.begin(), num.end()); *this = num * inverse(denom, n - m + 1); this->resize(n - m + 1); std::reverse(this->begin(), this->end()); return *this; } // Divides `*this` by `other` and assigns the remainder to `*this`. // Requires `other` to contain nonzero coefficients. fps& operator%=(const fps &other) { fps denom(other.begin(), other.end()); denom.strip(); assert(!denom.empty()); fps num(this->begin(), this->end()); num.strip(); int n = num.size(), m = denom.size(); if (n < m) return *this; std::reverse(denom.begin(), denom.end()); std::reverse(num.begin(), num.end()); fps quo = num * inverse(denom, n - m + 1); quo.resize(n - m + 1); std::reverse(quo.begin(), quo.end()); *this -= quo * other; this->resize(m - 1); return *this; } // Returns a `vector` containing the results of evaluating `*this` at each point in `vec`. std::vector eval(const std::vector &vec) { int m = vec.size(), len = 1; while (len < m) len *= 2; std::vector nodes(len * 2); for (int i = 0; i < m; i++) nodes[len + i] = {-vec[i], 1}; for (int i = m; i < len; i++) nodes[len + i] = {1}; for (int i = len - 1; i > 0; i--) nodes[i] = nodes[i * 2] * nodes[i * 2 + 1]; std::vector result(m); auto solve = [&](auto &solve, int i, fps poly) { if (i >= len + m) return; poly %= nodes[i]; if (i >= len) { result[i - len] = poly[0]; return; } solve(solve, i * 2, poly); solve(solve, i * 2 + 1, poly); }; solve(solve, 1, *this); return result; } // Returns the sum of `a` and `b`. friend fps operator+(const fps &a, const fps &b) { fps c = a; return c += b; } // Returns the difference of `a` and `b`. friend fps operator-(const fps &a, const fps &b) { fps c = a; return c -= b; } // Returns the product of `a` and `b`. friend fps operator*(const fps &a, const fps &b) { fps c = a; return c *= b; } // Returns `a` with its coefficients multiplied by `b`. friend fps operator*(const fps &a, const mint &b) { fps c = a; return c *= b; } // Returns `b` with its coefficients multiplied by `a`. friend fps operator*(const mint &a, const fps &b) { return b * a; } // Returns `a` with its coefficients divided by `b`. // Requires `b != 0`. friend fps operator/(const fps &a, const mint &b) { assert(b != 0); fps c = a; return c /= b; } // Returns the quotient of `a` and `b`. // Requires `b` to contain nonzero coefficients. friend fps operator/(const fps &a, const fps &b) { fps c = a; return c /= b; } // Returns the remainder of `a` and `b`. // Requires `b` to contain nonzero coefficients. friend fps operator%(const fps &a, const fps &b) { fps c = a; return c %= b; } // Returns the inverse of `f` up to the first `n` coefficients. // Requires `!f.empty()`. // Requires `f[0] != 0`. // Requires `n >= 0`. static fps inverse(const fps &f, int n) { assert(!f.empty()); assert(f[0] != 0); assert(n >= 0); if (n == 0) return {}; fps result{f[0].inv()}; int m = 1; int len = f.size(); while (m < n) { m = std::min(m * 2, n); fps sub(f.begin(), f.begin() + std::min(m, len)); if (m > len) sub.resize(m); fps prod = result * sub; prod.resize(m); prod[0] = 2 - prod[0]; for (int i = 1; i < m; i++) prod[i] = -prod[i]; result *= prod; result.resize(m); } result.resize(n); return result; } // Returns a `pair` containing the quotient and remainder of `f` and `g`. // Requires `g` to contain nonzero coefficients. static std::pair divmod(const fps &f, const fps &g) { fps denom(g.begin(), g.end()); denom.strip(); assert(!denom.empty()); fps num(f.begin(), f.end()); num.strip(); int n = num.size(), m = denom.size(); if (n < m) return {{}, f}; std::reverse(denom.begin(), denom.end()); std::reverse(num.begin(), num.end()); fps quo = num * inverse(denom, n - m + 1); quo.resize(n - m + 1); std::reverse(quo.begin(), quo.end()); std::reverse(num.begin(), num.end()); num -= quo * g; num.resize(m - 1); return {quo, num}; } // Returns the derivative of `f`. // Returns an empty vector if `f` is empty. static fps derivative(const fps &f) { if (f.empty()) return {}; fps result(f.begin() + 1, f.end()); for (std::size_t i = 0; i < result.size(); i++) result[i] *= i + 1; return result; } // Returns the integral of `f`. // Sets the `0`-th coefficent of the integral as `0`. // If `f` is empty, returns an empty vector. static fps integral(const fps &f) { if (f.empty()) return {}; int len = f.size(); fps result(len + 1); result[1] = 1; for (int i = 2, p = mint::mod(); i <= len; i++) { result[i] = p / i * -result[p % i]; } for (int i = 0; i < len; i++) result[i + 1] *= f[i]; return result; } // Returns the logarithm of `f` up to the first `n` coefficients. // Requires `!f.empty()`. // Requires `f[0] == 1`. // Requires `n >= 0`. static fps logarithm(const fps &f, int n) { assert(!f.empty()); assert(f[0] == 1); assert(n >= 0); if (n == 0) return {}; fps prod; if (int len = f.size(); len <= n) prod = derivative(f); else prod = derivative({f.begin(), f.begin() + n}); prod *= inverse(f, n - 1); prod.resize(n - 1); fps result = integral(prod); result.resize(n); return result; } // Returns the exponential of `f` up to the first `n` coefficients. // Requires `f.empty() || f[0] == 0`. // Requires `n >= 0`. static fps exponential(const fps &f, int n) { assert(f.empty() || f[0] == 0); assert(n >= 0); if (n == 0) return {}; fps result{1}; if (f.empty()) { result.resize(n); return result; } int m = 1; int len = f.size(); while (m < n) { m = std::min(m * 2, n); fps log = -logarithm(result, m); for (int i = 0; i < m && i < len; i++) log[i] += f[i]; log[0]++; result *= log; result.resize(m); } return result; } // Returns `f` raised to the specified `pow` up to the first `n` coefficients. // If `pow == 0`, the resulting `fps` is equivalent to `1`. // If `pow > 0 && f.empty()`, the resulting `fps` is equivalent to `0`. // Requires `pow >= 0`. // Requires `n >= 0`. static fps power(const fps &f, int64_t pow, int n) { assert(pow >= 0); assert(n >= 0); if (n == 0) return {}; if (pow == 0) { fps result(n); result[0] = 1; return result; } int d = -1; { int64_t len = f.size(); int64_t q = (n + pow - 1) / pow; if (q > len) q = len; for (int i = 0; i < q; i++) { if (f[i] == 0) continue; d = i; break; } if (d == -1) return fps(n); } int shift = d * pow; int len = f.size() - d; if (len > n - shift) len = n - shift; fps g(f.begin() + d, f.begin() + d + len); mint acc = g[0].pow(pow); g = logarithm(g / g[0], n - shift) * pow; g = exponential(g, n - shift) * acc; fps result(n); for (int i = 0; i + shift < n; i++) result[i + shift] = g[i]; return result; } // Computes the coefficient of the term with the specified degree `k` in the rational function. // Requires `!denominator.empty() && denominator[0] != 0`. // Requires `k >= 0`. // Reference: https://info.atcoder.jp/entry/algorithm_lectures/linearly_recurrent_sequence_kth_term static mint bostan_mori(fps numerator, fps denominator, int64_t k) { assert(!denominator.empty() && denominator[0] != 0); assert(k >= 0); if (numerator.empty()) return 0; while (k) { fps denom_neg = denominator; for (std::size_t i = 1; i < denom_neg.size(); i += 2) { denom_neg[i] = -denom_neg[i]; } numerator *= denom_neg; denominator *= denom_neg; fps new_num, new_denom; new_num.reserve((numerator.size() + 1) >> 1); new_denom.reserve((denominator.size() + 1) >> 1); for (std::size_t i = k & 1; i < numerator.size(); i += 2) new_num.push_back(numerator[i]); for (std::size_t i = 0; i < denominator.size(); i += 2) new_denom.push_back(denominator[i]); numerator = new_num; denominator = new_denom; k >>= 1; } return numerator[0] / denominator[0]; } // Computes term `a[k]` of a homogeneous linear recurrence `a` of order `n`. // More specifically, `recurrence` specifies coefficients `c` in the relation // `a[i] = c[0] * a[i - 1] + ... + c[n - 1] * a[i - n]`. // Returns `0` if `recurrence` and `init` are empty. // Requires `recurrence.size() == init.size()`. // Requires `k >= 0`. static mint solve_recurrence(const fps &recurrence, const fps &init, int64_t k) { assert(recurrence.size() == init.size()); assert(k >= 0); int n = recurrence.size(); if (n == 0) return 0; if (k < n) return init[k]; fps denominator(n + 1, 1); for (int i = 0; i < n; i++) denominator[i + 1] = -recurrence[i]; fps numerator = denominator * init; numerator.resize(n); return bostan_mori(numerator, denominator, k); } // Given a vector of pairs `{x_i, y_i}`, returns `f` such that `f(x_i) == y_i` for all `i`. // Requires `vec` to contain distinct `x_i`'s. static fps interpolate(const std::vector> &vec) { int m = vec.size(), len = 1; while (len < m) len *= 2; std::vector nodes(len * 2); for (int i = 0; i < m; i++) nodes[i + len] = {-vec[i].first, 1}; for (int i = m; i < len; i++) nodes[i + len] = {1}; for (int i = len - 1; i > 0; i--) nodes[i] = nodes[i * 2] * nodes[i * 2 + 1]; auto solve = [&](auto &solve, int i, fps poly) -> fps { if (i >= len + m) return {}; poly %= nodes[i]; if (i >= len) { assert(poly[0] != 0); return {vec[i - len].second / poly[0]}; } return solve(solve, i * 2, poly) * nodes[i * 2 + 1] + solve(solve, i * 2 + 1, poly) * nodes[i * 2]; }; return solve(solve, 1, fps::derivative(nodes[1])); } // Given `f(x)`, returns `f(y)` where `y == x + offset`. static fps taylor_shift(const fps &f, mint offset) { int len = f.size(); fps result(len, 1), p(len), q(len); for (int i = 2, p = mint::mod(); i < len; i++) { result[i] = p / i * -result[p % i]; } for (int i = 1; i < len; i++) result[i] *= result[i - 1]; mint acc = 1; for (int i = 0; i < len; i++) { p[len - 1 - i] = f[i] * acc; acc *= i + 1; } acc = 1; for (int i = 0; i < len; i++) { q[i] = result[i] * acc; acc *= offset; } fps r = p * q; for (int i = 0; i < len; i++) result[i] *= r[len - 1 - i]; return result; } }; } // namespace kotone #endif // KOTONE_FORMAL_POWER_SERIES_HPP // #include // https://github.com/amiast/cpp-utility #ifndef KOTONE_MODINT_UTILITY_HPP #define KOTONE_MODINT_UTILITY_HPP 1 #include #include // #include // https://github.com/amiast/cpp-utility namespace kotone { // Returns a length-`(n+1)` vector `reciprocal` such that `reciprocal[i]` is the modular inverse of `i`. // The value of `reciprocal[0]` is undefined. // Requires `mint::mod()` to be prime. // Requires `1 <= n < mint::mod()`. template std::vector reciprocals(int n) { int p = mint::mod(); assert(1 <= n && n <= p); std::vector result(n + 1); result[1] = 1; for (int i = 2; i <= n; i++) { result[i] = -(p / i) * result[p % i]; } return result; } // Returns a vector containing the first `n + 1` factorials (`0!, 1!, ..., n!`). // Requires `n >= 0`. template std::vector factorials(int n) { assert(n >= 0); std::vector result(n + 1); result[0] = 1; for (int i = 1; i <= n; i++) result[i] = i * result[i - 1]; return result; } // Returns a vector of inverse factorials given the vector of factorials. // Requires `vec_factorial` to match the format of the output of `factorials()`. // Requires `mint::mod()` to be prime. // Requires `1 <= vec_factorial.size() <= mint::mod()`. template std::vector inv_factorials(const std::vector &vec_factorial) { int len = vec_factorial.size(); int p = mint::mod(); assert(1 <= len && len <= p); std::vector result(len); assert(vec_factorial[len - 1] != 0); result[len - 1] = vec_factorial[len - 1].inv(); for (int i = len - 1; i > 0; i--) result[i - 1] = i * result[i]; return result; } // A wrapper class for combinatorial functions with modint. template struct modint_utility { private: std::vector _inv, _fact, _ifact; int _p = -1, _max_n = -1; void _build(int new_max) { if (new_max <= _max_n) return; _inv.resize(new_max + 1, 1); _fact.resize(new_max + 1, 1); _ifact.resize(new_max + 1, 1); for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) { _inv[i] = -(_p / i) * _inv[_p % i]; } for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _fact[i] = i * _fact[i - 1]; for (int i = std::max(_max_n + 1, 2); i <= new_max; i++) _ifact[i] = _inv[i] * _ifact[i - 1]; _max_n = new_max; } public: modint_utility() : _p(mint::mod()) {} // Instantiates with the first `n + 1` factorials (`0!, 1!, ..., n!`) precomputed. // Requires `mint::mod()` to be prime. // Requires `mint::mod()` to be invariant. // Requires `n < mint::mod()`. modint_utility(int n) { _p = mint::mod(); assert(n < _p); _build(n); } // Returns the modular inverse of `n`. // Requires `1 <= n < mint::mod()`. mint inv(int n) { assert(1 <= n && n < _p); if (n >= _max_n) _build(n); return _inv[n]; } // Returns `n!`. // Requires `0 <= n < mint::mod()`. mint factorial(int n) { assert(0 <= n && n < _p); if (n >= _max_n) _build(n); return _fact[n]; } // Returns the modular inverse of `n!`. // Requires `0 <= n < mint::mod()`. mint inv_factorial(int n) { assert(0 <= n && n < _p); if (n >= _max_n) _build(n); return _ifact[n]; } // Returns the number of permutations of `k` of `n` objects. // Requires `0 <= k <= n < mint::mod()`. mint perm(int n, int k) { assert(0 <= k && k <= n && n < _p); if (n >= _max_n) _build(n); return _fact[n] * _ifact[n - k]; } // Returns the number of combinations of `k` of `n` objects. // Requires `0 <= k <= n < mint::mod()`. mint comb(int n, int k) { assert(0 <= k && k <= n && n < _p); if (n >= _max_n) _build(n); return _fact[n] * _ifact[k] * _ifact[n - k]; } // Returns the `n`-th Catalan number. // Requires `0 <= n * 2 < _p`. mint catalan(int n) { assert(0 <= n && n * 2 < _p); if (n * 2 >= _max_n) _build(n * 2); return _fact[n * 2] * _ifact[n + 1] * _ifact[n]; } }; // Returns a square root of the given value. // If no square root exists, returns `0`. // If there are multiple square roots, the function may return any of them. template mint sqrt_mint(mint val) { if (val == 0) return 0; int mod = mint::mod(); if (mod == 2) return val; if (val.pow((mod - 1) / 2) == -1) return 0; if (mod % 4 == 3) return val.pow((mod + 1) / 4); int s = 0; int q = mod - 1; while (q % 2 == 0) { q /= 2; s++; } mint z = 2; while (z.pow((mod - 1) / 2) == 1) z++; mint c = z.pow(q); mint x = val.pow((q + 1) / 2); mint t = val.pow(q); while (t != 1) { int i = 0; mint tpow = t; while (tpow != 1 && i < s) { tpow *= tpow; i++; } if (i == s) return 0; mint b = c.pow(1 << (s - i - 1)); x *= b; t *= b * b; c = b * b; s = i; } return x; } } // namespace kotone #endif // KOTONE_MODINT_UTILITY_HPP using mint = atcoder::modint998244353; using fps = kotone::formal_power_series; int main() { int N; std::cin >> N; kotone::modint_utility util(N); fps f(N); for (int i = 0; i < N; i++) f[i] = util.inv_factorial(i) * (i + 1); mint result = fps::power(f, N, N - 1)[N - 2]; result *= util.factorial(N - 2); result /= mint(N).pow(N - 2); std::cout << result.val() << std::endl; }