//#define _GLIBCXX_DEBUG #include #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater >; const int INF = 0xccccccc; const ll LINF = 0xcccccccccccccccLL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} namespace fft { constexpr unsigned int modulo = 998244353; constexpr long double PI = 3.141592653589793238L; struct modint_base {}; template using is_modint = is_base_of; template using is_modint_t = enable_if_t::value>; template using is_complex = typename conditional>::value || is_same>::value, true_type, false_type>::type; //begin NTT template struct mint : modint_base { unsigned int x; static constexpr int mod() {return m;} static constexpr unsigned int umod() {return m;} mint():x(0) {} mint(int64_t x_) { int64_t v = int64_t(x_ % umod()); if(v < 0) v += umod(); x = (unsigned int)v; } static mint row(int v) { mint v_; v_.x = v; return v_; } mint operator-() const { return mint(-int64_t(x));} mint& operator+=(const mint a) { if ((x += a.x) >= umod()) x -= umod(); return *this; } mint& operator-=(const mint a) { if ((x += umod()-a.x) >= umod()) x -= umod(); return *this; } mint& operator*=(const mint a) { uint64_t z = x; z *= a.x; x = (unsigned int)(z % umod()); return *this; } mint operator+(const mint a) const { return mint(*this) += a;} mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} mint &operator++() { x++; if(x == umod()) x = 0; return *this; } mint &operator--() { if(x == 0) x = umod(); x--; return *this; } mint operator++(int) { mint result = *this; ++*this; return result; } mint operator--(int) { mint result = *this; --*this; return result; } mint pow(int64_t t) const { mint x_ = *this, r = 1; while(t) { if(t&1) r *= x_; x_ *= x_; t >>= 1; } return r; } mint inv() const { return pow(umod()-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) {return mint(*this) /= a;} friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;} friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;} friend istream &operator>>(istream &is, mint &x) {return is >> x.x;} friend ostream &operator<<(ostream &os, const mint &x) {return os << x.x;} }; constexpr int64_t safe_mod(int64_t x, int64_t m) { x %= m; if(x < 0) x += m; return x; } constexpr int64_t pow_mod_constexpr(int64_t x, int64_t n, int m) { if(m == 1) return 0; unsigned int _m = (unsigned int)(m); uint64_t r = 1; uint64_t y = safe_mod(x, m); while(n) { if(n&1) r = (r*y)%_m; y = (y*y)%_m; n >>= 1; } return r; } constexpr int primitive_root_constexpr(int m) { if(m == 2) return 1; if(m == 167772161) return 3; if(m == 469762049) return 3; if(m == 754974721) return 11; if(m == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (m-1)>>1; while(~x&1) x >>= 1; for(int i = 3; (int64_t)(i)*i <= x; i += 2) { if(x%i == 0) { divs[cnt++] = i; while(x%i == 0) x /= i; } } if(x > 1) divs[cnt++] = x; for(int g = 2;; g++) { bool ok = true; for(int i = 0; i < cnt; i++) { if(pow_mod_constexpr(g, (m-1)/divs[i], m) == 1) { ok = false; break; } } if(ok) return g; } } template constexpr int primitive_root = primitive_root_constexpr(m); constexpr pair inv_gcd(int64_t a, int64_t b) { a = safe_mod(a, b); if(a == 0) return {b, 0}; int64_t s = b, t = a; int64_t m0 = 0, m1 = 1; while(t) { int64_t u = s/t; s -= t*u; m0 -= m1*u; int64_t tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if(m0 < 0) m0 += b/s; return {s, m0}; } int ceil_pow2(int n) { int x = 0; while((1U << x) < (unsigned int)(n)) x++; return x; } template* = nullptr> void butterfly(vector &ary) { static constexpr int g = primitive_root; int n = int(ary.size()); int h = ceil_pow2(n); static bool first = true; static mint sum_e[30]; if(first) { first = false; mint es[30], ies[30]; int cnt2 = __builtin_ctz(mint::mod()-1); mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv(); for(int i = cnt2; i >= 2; i--) { es[i-2] = e; ies[i-2] = ie; e *= e; ie *= ie; } mint now(1); for(int i = 0; i <= cnt2-2; i++) { sum_e[i] = es[i] * now; now *= ies[i]; } } for(int ph = 1; ph <= h; ph++) { int w = 1<<(ph-1), p = 1<<(h-ph); mint now(1); for(int s = 0; s < w; s++) { int offset = s << (h-ph+1); for(int i = 0; i < p; i++) { mint l = ary[i+offset]; mint r = ary[i+offset+p] * now; ary[i+offset] = l+r; ary[i+offset+p] = l-r; } now *= sum_e[__builtin_ctz(~(unsigned int)(s))]; } } } template* = nullptr> void butterfly_inv(vector &ary) { static constexpr int g = primitive_root; int n = int(ary.size()); int h = ceil_pow2(n); static bool first = true; static mint sum_ie[30]; if(first) { first = false; mint es[30], ies[30]; int cnt2 = __builtin_ctz(mint::mod()-1); mint e = mint(g).pow((mint::mod()-1)>>cnt2), ie = e.inv(); for(int i = cnt2; i >= 2; i--) { es[i-2] = e; ies[i-2] = ie; e *= e; ie *= ie; } mint now(1); for(int i = 0; i <= cnt2-2; i++) { sum_ie[i] = ies[i] * now; now *= es[i]; } } for(int ph = h; ph >= 1; ph--) { int w = 1<<(ph-1), p = 1<<(h-ph); mint inow(1); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { mint l = ary[i+offset]; mint r = ary[i+offset+p]; ary[i+offset] = l+r; ary[i+offset+p] = (uint64_t)(mint::mod() + l.x - r.x) * inow.x; } inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))]; } } } template* = nullptr> vector convolution(vector a, vector b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; if(min(n, m) <= 60) { if(n < m) { swap(n, m); swap(a, b); } vector ans(n+m-1); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { ans[i+j] += a[i] * b[j]; } } return ans; } int z = 1<::value>* = nullptr> vector convolution(const vector &a, const vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; using Mint = mint; vector a2(n), b2(m); for(int i = 0; i < n; i++) { a2[i] = Mint(a[i]); } for(int i = 0; i < m; i++) { b2[i] = Mint(b[i]); } vector c2 = convolution(move(a2), move(b2)); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) c[i] = c2[i].x; return c; } vector convolution_ll(const vector &a, vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; static constexpr uint64_t MOD1 = 754974721; // 2^24 static constexpr uint64_t MOD2 = 167772161; // 2^25 static constexpr uint64_t MOD3 = 469762049; // 2^26 static constexpr uint64_t M2M3 = MOD2 * MOD3; static constexpr uint64_t M1M3 = MOD1 * MOD3; static constexpr uint64_t M1M2 = MOD1 * MOD2; static constexpr uint64_t M1M2M3 = MOD1 * MOD2 * MOD3; static constexpr uint64_t i1 = inv_gcd(M2M3, MOD1).second; static constexpr uint64_t i2 = inv_gcd(M1M3, MOD2).second; static constexpr uint64_t i3 = inv_gcd(M1M2, MOD3).second; vector c1 = convolution(a, b); vector c2 = convolution(a, b); vector c3 = convolution(a, b); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) { uint64_t x = 0; x += (c1[i] * i1) % MOD1 * M2M3; x += (c2[i] * i2) % MOD2 * M1M3; x += (c3[i] * i3) % MOD3 * M1M2; int64_t diff = c1[i] - safe_mod(int64_t(x), int64_t(MOD1)); if(diff < 0) diff += MOD1; static constexpr uint64_t offset[5] = {0, 0, M1M2M3, 2*M1M2M3, 3*M1M2M3}; x -= offset[diff%5]; c[i] = x; } return c; } //begin FFT template::value>* = nullptr> void butterfly(vector> &ary) { int n = int(ary.size()); int h = ceil_pow2(n); using Complex = complex; static bool first = true; static Complex sum_e[30]; if(first) { first = false; Complex now = 1.0; for(int i = 0; i < 28; i++) { Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1))); sum_e[i] = es * now; now *= conj(es); } } for(int ph = 1; ph <= h; ph++) { int w = 1<<(ph-1), p = 1<<(h-ph); Complex now = Complex(1.0, 0); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { Complex l = ary[i+offset]; Complex r = ary[i+offset+p] * now; ary[i+offset] = l+r; ary[i+offset+p] = l-r; } now *= sum_e[__builtin_ctz(~(unsigned int)(s))]; } } } template::value>* = nullptr> void butterfly_inv(vector> &ary) { int n = int(ary.size()); int h = ceil_pow2(n); using Complex = complex; static bool first = true; static Complex sum_ie[30]; if(first) { first = false; Complex now = 1.0; for(int i = 0; i < 28; i++) { Complex es = polar(Float(1.0), Float(PI)/(1<<(i+1))); sum_ie[i] = conj(es) * now; now *= es; } } for(int ph = h; ph >= 1; ph--) { int w = 1<<(ph-1), p = 1<<(h-ph); Complex inow = Complex(1.0, 0); for(int s = 0; s < w; s++) { int offset = s<<(h-ph+1); for(int i = 0; i < p; i++) { Complex l = ary[i+offset]; Complex r = ary[i+offset+p]; ary[i+offset] = l+r; ary[i+offset+p] = (l-r) * inow; } inow *= sum_ie[__builtin_ctz(~(unsigned int)(s))]; } } Complex in(1.0/n, 0); for(int i = 0; i < n; i++) ary[i] *= in; } template::value>* = nullptr> vector convolution(vector a, vector b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; if(min(n, m) <= 60) { if(n < m) { swap(n, m); swap(a, b); } vector ans(n+m-1); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { ans[i+j] += a[i] * b[j]; } } return ans; } int z = 1<::value>* = nullptr> vector convolution(vector &a, vector &b) { int n = int(a.size()), m = int(b.size()); if(!n || !m) return {}; using Complex = complex; vector a2(n), b2(m); for(int i = 0; i < n; i++) a2[i] = Complex(a[i], 0); for(int i = 0; i < m; i++) b2[i] = Complex(b[i], 0); vector c2 = convolution(move(a2), move(b2)); vector c(n+m-1); for(int i = 0; i < n+m-1; i++) c[i] = c2[i].real(); return c; } //modulo 998244353 //vector> convolution(vector>, vector>) //vector convolution(vector&, vector&) ##is_integral::value == true //vector convolution_ll(vector&, vector&) //vector convolution(vector, vector) //vector convolution(vector&, vector&) } // namespace fft template string to_string(fft::mint a) { return to_string(a.x); } #define USE_NTT //#define USE_ll_TYPE //(convolution_llの引数の参照を取る必要あり & 割り算無理) template struct FPS : vector { using vector::vector; using vector::operator=; FPS operator-() const { int n = (*this).size(); FPS res(n); for(int i = 0; i < n; i++) res[i] = -(*this)[i]; return res; } FPS &operator+=(const FPS &a) { int n = (*this).size(); int m = a.size(); this->resize(max(n, m)); for(int i = 0; i < m; i++) (*this)[i] += a[i]; return *this; } FPS &operator-=(const FPS &a) { int n = (*this).size(); int m = a.size(); this->resize(max(n, m)); for(int i = 0; i < m; i++) (*this)[i] -= a[i]; return *this; } #ifdef USE_NTT FPS &operator*=(const FPS &a) { #ifdef USE_ll_TYPE *this = fft::convolution_ll(*this, a); #else *this = fft::convolution(*this, a); #endif return *this; } FPS &operator/=(const FPS &a) { int n = (*this).size(); int m = a.size(); *this = fft::convolution(*this, a.inv(max(n, m))); this->resize(n); return *this; } FPS inv(int d = -1) const { int n =(*this).size(); assert(n > 0 and (*this)[0] != 0); if(d == -1) d = n; FPS res{T(1)/(*this)[0]}; res.reserve(1<resize(n+m-1); for(int i = n+m-2; i >= 0; i--) { (*this)[i] *= a[0]; for(int j = 1; j < min(i+1, m); j++) { (*this)[i] += (*this)[i-j] * a[j]; } } return (*this); } FPS &operator/=(const FPS &a) { int n = (*this).size(); int m = a.size(); assert(a[0] != T(0)); for(int i = 0; i < n; i++) { for(int j = 1; j < min(i+1, m); j++) { (*this)[i] -= (*this)[i-j] * a[j]; } (*this)[i] /= a[0]; } return *this; } #endif FPS &operator<<=(int r) { (*this).insert(begin(*this), r, 0); return *this; } FPS &operator>>=(int r) { (*this).erase(begin(*this), begin(*this)+min(int((*this).size()), r)); return *this; } friend FPS operator+(const FPS &lhs, const FPS &rhs) { return FPS(lhs) += rhs; } friend FPS operator-(const FPS &lhs, const FPS &rhs) { return FPS(lhs) -= rhs; } friend FPS operator*(const FPS &lhs, const FPS &rhs) { return FPS(lhs) *= rhs; } friend FPS operator/(const FPS &lhs, const FPS &rhs) { return FPS(lhs) /= rhs; } friend FPS operator<<(const FPS &lhs, const int rhs) { return FPS(lhs) <<= rhs; } friend FPS operator>>(const FPS &lhs, const int rhs) { return FPS(lhs) >>= rhs; } // g is considered to be sorted void mul(vector> g) { int n = (*this).size(); int d; T c; tie(d, c) = g[0]; if(d == 0) g.erase(g.begin()); else c = 0; for(int i = n-1; i >= 0; i--) { (*this)[i] *= c; for(auto &p:g) { if(p.first > i) break; (*this)[i] += (*this)[i-p.first] * p.second; } } } void div(vector> g) { int n = (*this).size(); int d; T c; tie(d, c) = g[0]; assert(d == 0 and c != T(0)); g.erase(g.begin()); c = T(1)/c; for(int i = 0; i < n; i++) { for(auto p:g) { if(p.first > i) break; (*this)[i] -= (*this)[i-p.first] * p.second; } (*this)[i] *= c; } } void mul(int d, T c) { // *(1 + cx^d) int n = (*this).size(); for(int i = n-1; i >= d; i--) { (*this)[i] += (*this)[i-d] * c; } } void div(int d, T c) { // /(1 + cx^d) int n = (*this).size(); for(int i = 0; i < n-d; i++) { (*this)[i+d] -= (*this)[i] * c; } } }; //head template FPS pow(FPS &a, int p) { int n = a.size(); FPS res(1, 1), r = a; while(p) { if(p&1) res *= r; r *= r; p >>= 1; res.resize(n); r.resize(n); } return res; } using Mint = fft::mint; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; FPS v(n-1); iota(all(v), 1); Mint now(1); for(int i = 1; i < n-1; i++) { now *= i; v[i] /= now; } v = pow(v, n); cout << v[n-2]*now/Mint(n).pow(n-2) << endl; }