結果
問題 | No.1302 Random Tree Score |
ユーザー |
👑 |
提出日時 | 2023-06-01 01:09:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 394 ms / 3,000 ms |
コード長 | 35,226 bytes |
コンパイル時間 | 5,417 ms |
コンパイル使用メモリ | 276,368 KB |
実行使用メモリ | 15,512 KB |
最終ジャッジ日時 | 2024-12-28 14:22:03 |
合計ジャッジ時間 | 8,976 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
// start A.cpp// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));#ifndef RIN__LOCAL#define endl "\n"#endif#define spa ' '#define len(A) A.size()#define all(A) begin(A), end(A)#define fori1(a) for (ll _ = 0; _ < (a); _++)#define fori2(i, a) for (ll i = 0; i < (a); i++)#define fori3(i, a, b) for (ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)vector<char> stoc(string &S) {int n = S.size();vector<char> ret(n);for (int i = 0; i < n; i++) ret[i] = S[i];return ret;}#define INT(...)\int __VA_ARGS__;\inp(__VA_ARGS__);#define LL(...)\ll __VA_ARGS__;\inp(__VA_ARGS__);#define STRING(...)\string __VA_ARGS__;\inp(__VA_ARGS__);#define CHAR(...)\char __VA_ARGS__;\inp(__VA_ARGS__);#define VEC(T, A, n)\vector<T> A(n);\inp(A);#define VVEC(T, A, n, m)\vector<vector<T>> A(n, vector<T>(m));\inp(A);const ll MOD1 = 1000000007;const ll MOD9 = 998244353;template <class T>auto min(const T &a) {return *min_element(all(a));}template <class T>auto max(const T &a) {return *max_element(all(a));}template <class T, class S>auto clamp(T &a, const S &l, const S &r) {return (a > r ? r : a < l ? l : a);}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}template <class T, class S>inline bool chclamp(T &a, const S &l, const S &r) {auto b = clamp(a, l, r);return (a != b ? a = b, 1 : 0);}void FLUSH() {cout << flush;}void print() {cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(forward<Tail>(tail)...);}template <typename T>void print(vector<T> &A) {int n = A.size();for (int i = 0; i < n; i++) {cout << A[i];if (i != n - 1) cout << ' ';}cout << endl;}template <typename T>void print(vector<vector<T>> &A) {for (auto &row : A) print(row);}template <typename T, typename S>void print(pair<T, S> &A) {cout << A.first << spa << A.second << endl;}template <typename T, typename S>void print(vector<pair<T, S>> &A) {for (auto &row : A) print(row);}template <typename T, typename S>void prisep(vector<T> &A, S sep) {int n = A.size();for (int i = 0; i < n; i++) {cout << A[i];if (i != n - 1) cout << sep;}cout << endl;}template <typename T, typename S>void priend(T A, S end) {cout << A << end;}template <typename T>void priend(T A) {priend(A, spa);}template <class... T>void inp(T &... a) {(cin >> ... >> a);}template <typename T>void inp(vector<T> &A) {for (auto &a : A) cin >> a;}template <typename T>void inp(vector<vector<T>> &A) {for (auto &row : A) inp(row);}template <typename T, typename S>void inp(pair<T, S> &A) {inp(A.first, A.second);}template <typename T, typename S>void inp(vector<pair<T, S>> &A) {for (auto &row : A) inp(row.first, row.second);}template <typename T>T sum(vector<T> &A) {T tot = 0;for (auto a : A) tot += a;return tot;}template <typename T>vector<T> compression(vector<T> X) {sort(all(X));X.erase(unique(all(X)), X.end());return X;}vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {vector<vector<int>> edges(n, vector<int>());for (int i = 0; i < m; i++) {INT(u, v);u -= indexed;v -= indexed;edges[u].push_back(v);if (!direct) edges[v].push_back(u);}return edges;}vector<vector<int>> read_tree(int n, int indexed = 1) {return read_edges(n, n - 1, false, indexed);}template <typename T>vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());for (int i = 0; i < m; i++) {INT(u, v);T w;inp(w);u -= indexed;v -= indexed;edges[u].push_back({v, w});if (!direct) edges[v].push_back({u, w});}return edges;}template <typename T>vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {return read_wedges<T>(n, n - 1, false, indexed);}inline bool yes(bool f = true) {cout << (f ? "yes" : "no") << endl;return f;}inline bool Yes(bool f = true) {cout << (f ? "Yes" : "No") << endl;return f;}inline bool YES(bool f = true) {cout << (f ? "YES" : "NO") << endl;return f;}inline bool no(bool f = true) {cout << (!f ? "yes" : "no") << endl;return f;}inline bool No(bool f = true) {cout << (!f ? "Yes" : "No") << endl;return f;}inline bool NO(bool f = true) {cout << (!f ? "YES" : "NO") << endl;return f;}// start other/Modint.hpptemplate <int MOD>struct Modint {int x;Modint() : x(0) {}Modint(int64_t y) {if (y >= 0)x = y % MOD;elsex = (y % MOD + MOD) % MOD;}Modint &operator+=(const Modint &p) {x += p.x;if (x >= MOD) x -= MOD;return *this;}Modint &operator-=(const Modint &p) {x -= p.x;if (x < 0) x += MOD;return *this;}Modint &operator*=(const Modint &p) {x = int(1LL * x * p.x % MOD);return *this;}Modint &operator/=(const Modint &p) {*this *= p.inverse();return *this;}Modint &operator%=(const Modint &p) {assert(p.x == 0);return *this;}Modint operator-() const {return Modint(-x);}Modint &operator++() {x++;if (x == MOD) x = 0;return *this;}Modint &operator--() {if (x == 0) x = MOD;x--;return *this;}Modint operator++(int) {Modint result = *this;++*this;return result;}Modint operator--(int) {Modint result = *this;--*this;return result;}friend Modint operator+(const Modint &lhs, const Modint &rhs) {return Modint(lhs) += rhs;}friend Modint operator-(const Modint &lhs, const Modint &rhs) {return Modint(lhs) -= rhs;}friend Modint operator*(const Modint &lhs, const Modint &rhs) {return Modint(lhs) *= rhs;}friend Modint operator/(const Modint &lhs, const Modint &rhs) {return Modint(lhs) /= rhs;}friend Modint operator%(const Modint &lhs, const Modint &rhs) {assert(rhs.x == 0);return Modint(lhs);}bool operator==(const Modint &p) const {return x == p.x;}bool operator!=(const Modint &p) const {return x != p.x;}bool operator<(const Modint &rhs) const {return x < rhs.x;}bool operator<=(const Modint &rhs) const {return x <= rhs.x;}bool operator>(const Modint &rhs) const {return x > rhs.x;}bool operator>=(const Modint &rhs) const {return x >= rhs.x;}Modint inverse() const {int a = x, b = MOD, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Modint(u);}Modint pow(int64_t k) const {Modint ret(1);Modint y(x);while (k > 0) {if (k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Modint &p) {return os << p.x;}friend istream &operator>>(istream &is, Modint &p) {int64_t y;is >> y;p = Modint<MOD>(y);return (is);}static int get_mod() {return MOD;}};struct Arbitrary_Modint {int x;static int MOD;static void set_mod(int mod) {MOD = mod;}Arbitrary_Modint() : x(0) {}Arbitrary_Modint(int64_t y) {if (y >= 0)x = y % MOD;elsex = (y % MOD + MOD) % MOD;}Arbitrary_Modint &operator+=(const Arbitrary_Modint &p) {x += p.x;if (x >= MOD) x -= MOD;return *this;}Arbitrary_Modint &operator-=(const Arbitrary_Modint &p) {x -= p.x;if (x < 0) x += MOD;return *this;}Arbitrary_Modint &operator*=(const Arbitrary_Modint &p) {x = int(1LL * x * p.x % MOD);return *this;}Arbitrary_Modint &operator/=(const Arbitrary_Modint &p) {*this *= p.inverse();return *this;}Arbitrary_Modint &operator%=(const Arbitrary_Modint &p) {assert(p.x == 0);return *this;}Arbitrary_Modint operator-() const {return Arbitrary_Modint(-x);}Arbitrary_Modint &operator++() {x++;if (x == MOD) x = 0;return *this;}Arbitrary_Modint &operator--() {if (x == 0) x = MOD;x--;return *this;}Arbitrary_Modint operator++(int) {Arbitrary_Modint result = *this;++*this;return result;}Arbitrary_Modint operator--(int) {Arbitrary_Modint result = *this;--*this;return result;}friend Arbitrary_Modint operator+(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {return Arbitrary_Modint(lhs) += rhs;}friend Arbitrary_Modint operator-(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {return Arbitrary_Modint(lhs) -= rhs;}friend Arbitrary_Modint operator*(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {return Arbitrary_Modint(lhs) *= rhs;}friend Arbitrary_Modint operator/(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {return Arbitrary_Modint(lhs) /= rhs;}friend Arbitrary_Modint operator%(const Arbitrary_Modint &lhs, const Arbitrary_Modint &rhs) {assert(rhs.x == 0);return Arbitrary_Modint(lhs);}bool operator==(const Arbitrary_Modint &p) const {return x == p.x;}bool operator!=(const Arbitrary_Modint &p) const {return x != p.x;}bool operator<(const Arbitrary_Modint &rhs) {return x < rhs.x;}bool operator<=(const Arbitrary_Modint &rhs) {return x <= rhs.x;}bool operator>(const Arbitrary_Modint &rhs) {return x > rhs.x;}bool operator>=(const Arbitrary_Modint &rhs) {return x >= rhs.x;}Arbitrary_Modint inverse() const {int a = x, b = MOD, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;u -= t * v;swap(a, b);swap(u, v);}return Arbitrary_Modint(u);}Arbitrary_Modint pow(int64_t k) const {Arbitrary_Modint ret(1);Arbitrary_Modint y(x);while (k > 0) {if (k & 1) ret *= y;y *= y;k >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Arbitrary_Modint &p) {return os << p.x;}friend istream &operator>>(istream &is, Arbitrary_Modint &p) {int64_t y;is >> y;p = Arbitrary_Modint(y);return (is);}static int get_mod() {return MOD;}};int Arbitrary_Modint::MOD = 998244353;using modint9 = Modint<998244353>;using modint1 = Modint<1000000007>;using modint = Arbitrary_Modint;// end other/Modint.hpp// restart A.cppusing mint = modint9;// start math/Combination.hpptemplate <typename T>struct Combination {int N;vector<T> fact, invfact;Combination(int N) : N(N) {fact.resize(N + 1);invfact.resize(N + 1);fact[0] = 1;for (int i = 1; i <= N; i++) {fact[i] = fact[i - 1] * i;}invfact[N] = T(1) / fact[N];for (int i = N - 1; i >= 0; i--) {invfact[i] = invfact[i + 1] * (i + 1);}}void extend(int n) {int le = fact.size();fact.resize(n + 1);invfact.resize(n + 1);for (int i = le; i <= n; i++) {fact[i] = fact[i - 1] * i;}invfact[n] = T(1) / fact[n];for (int i = n - 1; i >= le; i--) {invfact[i] = invfact[i + 1] * (i + 1);}}T nCk(int n, int k) {if (k > n || k < 0) return T(0);if (n >= fact.size()) extend(n);return fact[n] * invfact[k] * invfact[n - k];}T nPk(int n, int k) {if (k > n || k < 0) return T(0);if (n >= fact.size()) extend(n);return fact[n] * invfact[n - k];}T nHk(int n, int k) {if (n == 0 && k == 0) return T(1);return nCk(n + k - 1, k);}T Catalan(int n) {return nCk(2 * n, n) - nCk(2 * n, n + 1);}// n 個の +1, m 個の -1, 累積和が常にk以下T Catalan(int n, int m, int k) {if (n > m + k || k < 0)return T(0);elsereturn nCk(n + m, n) - nCk(n + m, m + k + 1);}};// end math/Combination.hpp// restart A.cpp// start polynomial/FormalPowerSeries.hpp// start convolution/NTT.hpptemplate <typename mint>struct NumberTheoreticTransform {static vector<mint> roots, iroots, rate3, irate3;static int max_base;NumberTheoreticTransform() = default;static void init() {if (!roots.empty()) return;const unsigned mod = mint::get_mod();auto tmp = mod - 1;max_base = 0;while (tmp % 2 == 0) {tmp >>= 1;max_base++;}mint root = 2;while (root.pow((mod - 1) >> 1) == 1) root++;roots.resize(max_base + 1);iroots.resize(max_base + 1);rate3.resize(max_base + 1);irate3.resize(max_base + 1);roots[max_base] = root.pow((mod - 1) >> max_base);iroots[max_base] = mint(1) / roots[max_base];for (int i = max_base - 1; i >= 0; i--) {roots[i] = roots[i + 1] * roots[i + 1];iroots[i] = iroots[i + 1] * iroots[i + 1];}mint prod = 1, iprod = 1;for (int i = 0; i <= max_base - 3; i++) {rate3[i] = roots[i + 3] * prod;irate3[i] = iroots[i + 3] * iprod;prod *= iroots[i + 3];iprod *= roots[i + 3];}}static void ntt(vector<mint> &A) {init();int n = A.size();int h = __builtin_ctz(n);int le = 0;mint imag = roots[2];if (h & 1) {int p = 1 << (h - 1);for (int i = 0; i < p; i++) {auto r = A[i + p];A[i + p] = A[i] - r;A[i] += r;}le++;}for (; le + 1 < h; le += 2) {int p = 1 << (h - le - 2);for (int i = 0; i < p; i++) {auto a0 = A[i];auto a1 = A[i + p];auto a2 = A[i + 2 * p];auto a3 = A[i + 3 * p];auto a1na3imag = (a1 - a3) * imag;A[i] = a0 + a2 + a1 + a3;A[i + p] = a0 + a2 - (a1 + a3);A[i + 2 * p] = a0 - a2 + a1na3imag;A[i + 3 * p] = a0 - a2 - a1na3imag;}mint rot = rate3[0];for (int s = 1; s < (1 << le); s++) {int offset = s << (h - le);mint rot2 = rot * rot;mint rot3 = rot2 * rot;for (int i = 0; i < p; i++) {auto a0 = A[i + offset];auto a1 = A[i + offset + p] * rot;auto a2 = A[i + offset + 2 * p] * rot2;auto a3 = A[i + offset + 3 * p] * rot3;auto a1na3imag = (a1 - a3) * imag;A[i + offset] = a0 + a2 + a1 + a3;A[i + offset + p] = a0 + a2 - (a1 + a3);A[i + offset + 2 * p] = a0 - a2 + a1na3imag;A[i + offset + 3 * p] = a0 - a2 - a1na3imag;}rot *= rate3[__builtin_ctz(~s)];}}}static void intt(vector<mint> &A, bool f = true) {init();int n = A.size();int h = __builtin_ctz(n);int le = h;mint iimag = iroots[2];for (; le > 1; le -= 2) {int p = 1 << (h - le);for (int i = 0; i < p; i++) {auto a0 = A[i];auto a1 = A[i + p];auto a2 = A[i + 2 * p];auto a3 = A[i + 3 * p];auto a2na3iimag = (a2 - a3) * iimag;A[i] = a0 + a1 + a2 + a3;A[i + p] = a0 - a1 + a2na3iimag;A[i + 2 * p] = a0 + a1 - (a2 + a3);A[i + 3 * p] = a0 - a1 - a2na3iimag;}mint irot = irate3[0];for (int s = 1; s < (1 << (le - 2)); s++) {int offset = s << (h - le + 2);mint irot2 = irot * irot;mint irot3 = irot2 * irot;for (int i = 0; i < p; i++) {auto a0 = A[i + offset];auto a1 = A[i + offset + p];auto a2 = A[i + offset + 2 * p];auto a3 = A[i + offset + 3 * p];auto a2na3iimag = (a2 - a3) * iimag;A[i + offset] = a0 + a1 + a2 + a3;A[i + offset + p] = (a0 - a1 + a2na3iimag) * irot;A[i + offset + 2 * p] = (a0 + a1 - (a2 + a3)) * irot2;A[i + offset + 3 * p] = (a0 - a1 - a2na3iimag) * irot3;}irot *= irate3[__builtin_ctz(~s)];}}if (le >= 1) {int p = 1 << (h - 1);for (int i = 0; i < p; i++) {auto ajp = A[i] - A[i + p];A[i] += A[i + p];A[i + p] = ajp;}}if (f) {mint inv = mint(1) / n;for (int i = 0; i < n; i++) {A[i] *= inv;}}}static vector<mint> multiply(vector<mint> A, vector<mint> B) {int need = A.size() + B.size() - 1;if (min(A.size(), B.size()) < 60) {vector<mint> C(need, 0);for (int i = 0; i < A.size(); i++)for (int j = 0; j < B.size(); j++) {C[i + j] += A[i] * B[j];}return C;}int sz = 1;while (sz < need) sz <<= 1;A.resize(sz, 0);B.resize(sz, 0);ntt(A);ntt(B);mint inv = mint(1) / sz;for (int i = 0; i < sz; i++) A[i] *= B[i] * inv;intt(A, false);A.resize(need);return A;}};template <typename mint>vector<mint> NumberTheoreticTransform<mint>::roots = vector<mint>();template <typename mint>vector<mint> NumberTheoreticTransform<mint>::iroots = vector<mint>();template <typename mint>vector<mint> NumberTheoreticTransform<mint>::rate3 = vector<mint>();template <typename mint>vector<mint> NumberTheoreticTransform<mint>::irate3 = vector<mint>();template <typename mint>int NumberTheoreticTransform<mint>::max_base = 0;// end convolution/NTT.hpp// restart polynomial/FormalPowerSeries.hpp// start math/cipolla.hpp// start math/modpow.hpptemplate <typename T>T modpow(T a, long long b, T MOD) {T ret = 1;while (b > 0) {if (b & 1) {ret *= a;ret %= MOD;}a *= a;a %= MOD;b >>= 1;}return ret;}// end math/modpow.hpp// restart math/cipolla.hpplong long cipolla(long long a, long long MOD) {if (MOD == 2)return a;else if (a == 0)return 0;else if (modpow(a, (MOD - 1) / 2, MOD) != 1)return -1;long long b = 1;while (modpow((b * b + MOD - a) % MOD, (MOD - 1) / 2, MOD) == 1) {b++;}long long base = (b * b + MOD - a) % MOD;auto multi = [&](long long a0, long long b0, long long a1, long long b1) -> pair<long long, long long> { return {(a0 * a1 + (b0 * b1 % MOD)* base) % MOD, (a0 * b1 + b0 * a1) % MOD}; };auto pow_ = [&](auto self, long long a, long long b, long long n) -> pair<long long, long long> {if (n == 0) return {1, 0};auto tmp = multi(a, b, a, b);auto ret = self(self, tmp.first, tmp.second, n / 2);if (n & 1) {ret = multi(ret.first, ret.second, a, b);}return ret;};return pow_(pow_, b, 1LL, (MOD + 1) / 2).first;}// end math/cipolla.hpp// restart polynomial/FormalPowerSeries.hpptemplate <typename mint>struct FormalPowerSeries : vector<mint> {using vector<mint>::vector;using FPS = FormalPowerSeries;static vector<mint> inv_x;void shrink() {while (this->size() && this->back() == mint(0)) {this->pop_back();}}FPS &operator+=(const FPS &A) {if (A.size() > this->size()) this->resize(A.size());for (int i = 0; i < A.size(); i++) (*this)[i] += A[i];return *this;}FPS &operator+=(const mint &x) {if (this->empty()) this->resize(1);(*this)[0] += x;return *this;}FPS &operator-=(const FPS &A) {if (A.size() > this->size()) this->resize(A.size());for (int i = 0; i < A.size(); i++) (*this)[i] -= A[i];return *this;}FPS &operator-=(const mint &x) {if (this->empty()) this->resize(1);(*this)[0] -= x;return *this;}FPS &operator*=(const FPS &A) {if (this->empty() || A.empty()) {this->clear();return *this;}auto res = NumberTheoreticTransform<mint>::multiply(*this, A);return *this = {begin(res), end(res)};}FPS &operator*=(const mint &x) {for (int i = 0; i < this->size(); i++) (*this)[i] *= x;return *this;}FPS operator+(const FPS &A) const {return FPS(*this) += A;}FPS operator+(const mint &x) const {return FPS(*this) += x;}FPS operator-(const FPS &A) const {return FPS(*this) -= A;}FPS operator-(const mint &x) const {return FPS(*this) -= x;}FPS operator*(const FPS &A) const {return FPS(*this) *= A;}FPS operator*(const mint &x) const {return FPS(*this) *= x;}FPS operator-() const {FPS ret(this->size);for (int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];return ret;}FPS inv(int deg = -1) {assert((*this)[0] != mint(0));if (deg == -1) deg = this->size();FPS g = {mint(1) / (*this)[0]};int l = 1;while (l < deg) {FPS tmp = g * 2;l <<= 1;FPS tmp2;g *= g;if (this->size() >= l)tmp2 = FPS({this->begin(), this->begin() + l}) * g;elsetmp2 = (*this) * g;g = tmp - tmp2;g.resize(l);}g.resize(deg);return g;}void iinv(int deg = -1) {*this = inv(deg);}FPS differential() {FPS ret(this->size() - 1);for (int i = 0; i < this->size() - 1; i++) ret[i] = (*this)[i + 1] * (i + 1);return ret;}void idifferential() {*this = this->differential();}void extend_inv(int n) {int bn = inv_x.size();if (n >= bn) {inv_x.resize(n + 1, 0);if (bn == 0) {inv_x[0] = 0;inv_x[1] = 1;bn = 2;}ll mod = mint::get_mod();for (int i = bn; i <= n; i++) {inv_x[i] = mod - inv_x[mod % i].x * (mod / i) % mod;}}}FPS integral() {extend_inv(this->size());FPS ret(this->size() + 1);for (int i = 0; i < this->size(); i++) ret[i + 1] = (*this)[i] * inv_x[i + 1];return ret;}void iintegral() {*this = this->integral();}FPS log(int deg = -1) {assert((*this)[0] == mint(1));if (deg == -1) deg = this->size();FPS B = (this->differential()) * (this->inv());B.resize(deg - 1);return B.integral();}void ilog(int deg = -1) {*this = this->log(deg);}FPS exp(int deg = -1) {assert((*this)[0] == mint(0));if (deg == -1) deg = this->size();FPS g = {1};int l = 1;while (l < deg * 2) {l *= 2;FPS tmp = {1};tmp -= g.log(l);if (this->size() >= l)tmp += FPS({this->begin(), this->begin() + l});elsetmp += (*this);g *= tmp;g.resize(l);}g.resize(deg);return g;}void iexp(int deg = -1) {*this = this->exp(deg);}FPS pow(long long k, int deg = -1) {if (deg == -1) deg = this->size();if (k == 0) {FPS ret(deg, 0);ret[0] = 1;return ret;}int p = -1;for (int i = 0; i < deg; i++) {if ((*this)[i] != 0) {p = i;break;}}if (p == -1 || p > deg / k) {FPS ret(deg, 0);return ret;}mint inv = mint(1) / (*this)[p];FPS A = FPS({(*this).begin() + p, (*this).end()});A *= inv;A.ilog(deg);A *= k % mint::get_mod();A.iexp(deg);FPS B(p * k, 0);B.insert(B.end(), A.begin(), A.begin() + (deg - p * k));B *= (*this)[p].pow(k);return B;}void ipow(long long k, int deg = -1) {*this = this->pow(k, deg);}FPS sqrt(int deg = -1) {if (deg == -1) deg = this->size();if (this->size() == 0) {FPS ret(deg, 0);return ret;}if ((*this)[0] == mint(0)) {for (int i = 1; i < this->size(); i++) {if ((*this)[i] != 0) {if (i & 1) {FPS ret;return ret;}if (deg <= i / 2) break;FPS ret = FPS({this->begin() + i, this->end()}).sqrt(deg - i / 2);if (ret.size() == 0) return ret;FPS ret2(i / 2, 0);ret2.insert(ret2.end(), ret.begin(), ret.end());swap(ret, ret2);if (ret.size() < deg) ret.resize(deg);return ret;}}FPS ret(deg, 0);return ret;}ll sq = cipolla((*this)[0].x, mint::get_mod());if (sq == -1) {FPS ret;return ret;}mint inv2 = mint(1) / 2;FPS g = {sq};int l = 1;while (l < deg) {l *= 2;if (this->size() >= l)g += FPS({this->begin(), this->begin() + l}) * g.inv(l);elseg += (*this) * g.inv(l);g *= inv2;}g.resize(deg);return g;}void isqrt(int deg = -1) {*this = this->sqrt(deg);}FPS taylorshift(mint a) {auto A = (*this);int deg = A.size();extend_inv(deg);mint fac = 1;for (int i = 0; i < deg; i++) {A[i] *= fac;fac *= (i + 1);}reverse(A.begin(), A.end());FPS g(deg, 0);g[0] = 1;for (int i = 1; i < deg; i++) g[i] = g[i - 1] * a * inv_x[i];A *= g;if (A.size() > deg) A.resize(deg);reverse(A.begin(), A.end());mint invfac = 1;for (int i = 0; i < deg; i++) {A[i] *= invfac;invfac *= inv_x[i + 1];}return A;}void itaylorshift(mint a) {int deg = this->size();extend_inv(deg);mint fac = 1;for (int i = 0; i < deg; i++) {(*this)[i] *= fac;fac *= (i + 1);}reverse(this->begin(), this->end());FPS g(deg, 0);g[0] = 1;for (int i = 1; i < deg; i++) g[i] = g[i - 1] * a * inv_x[i];(*this) *= g;if (this->size() > deg) this->resize(deg);reverse(this->begin(), this->end());mint invfac = 1;for (int i = 0; i < deg; i++) {(*this)[i] *= invfac;invfac *= inv_x[i + 1];}}pair<FPS, FPS> division_of_polynomial(FPS G) {FPS F = *this;if (F.size() < G.size()) {return {{}, F};}reverse(F.begin(), F.end());reverse(G.begin(), G.end());int deg = F.size() - G.size() + 1;auto Q = F * G.inv(deg);if (Q.size() > deg) Q.resize(deg);reverse(Q.begin(), Q.end());reverse(F.begin(), F.end());reverse(G.begin(), G.end());auto R = F - G * Q;R.shrink();return {Q, R};}vector<mint> multipoint_evaluation(vector<mint> &X) {int m = X.size();int m2 = 1;while (m2 <= m - 1) m2 *= 2;vector<FPS> G(m2 << 1, FPS(1, 1));for (int i = 0; i < m; i++) G[m2 + i] = {-X[i], 1};for (int i = m2 - 1; i >= 0; i--) G[i] = G[i << 1] * G[(i << 1) | 1];G[1] = this->division_of_polynomial(G[1]).second;for (int i = 2; i < m2 + m; i++) G[i] = G[i >> 1].division_of_polynomial(G[i]).second;vector<mint> Y(m);for (int i = 0; i < m; i++) {if (G[m2 + i].empty())Y[i] = 0;elseY[i] = G[m2 + i][0];}return Y;}vector<long long> multipoint_evaluation(vector<long long> &X) {int m = X.size();int m2 = 1;while (m2 <= m - 1) m2 *= 2;vector<FPS> G(m2 << 1, FPS(1, 1));for (int i = 0; i < m; i++) G[m2 + i] = {-X[i], 1};for (int i = m2 - 1; i >= 0; i--) G[i] = G[i << 1] * G[(i << 1) | 1];G[1] = this->division_of_polynomial(G[1]).second;for (int i = 2; i < m2 + m; i++) G[i] = G[i >> 1].division_of_polynomial(G[i]).second;vector<long long> Y(m);for (int i = 0; i < m; i++) {if (G[m2 + i].empty())Y[i] = 0;elseY[i] = G[m2 + i][0].x;}return Y;}friend ostream &operator<<(ostream &os, const FPS &A) {for (int i = 0; i < A.size(); i++) {os << A[i];if (i != A.size() - 1) os << ' ';}return os;}friend istream &operator>>(istream &is, FPS &A) {for (int i = 0; i < A.size(); i++) {is >> A[i];}return (is);}};template <typename mint>vector<mint> FormalPowerSeries<mint>::inv_x = vector<mint>();// end polynomial/FormalPowerSeries.hpp// restart A.cppusing FPS = FormalPowerSeries<mint>;void solve() {LL(n);FPS F(n);Combination<mint> C(n + 10);fori(i, n) {F[i] = C.invfact[i] * (i + 1);}F = F.pow(n);mint ans = F[n - 2] * C.fact[n - 2];ans /= mint(n).pow(n - 2);print(ans);}int main() {cin.tie(0)->sync_with_stdio(0);// cout << fixed << setprecision(12);int t;t = 1;// cin >> t;while (t--) solve();return 0;}// end A.cpp