#pragma GCC optimize("Ofast") #include "bits/stdc++.h" // Begin Header {{{ using namespace std; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template > using MaxHeap = priority_queue, Compare>; template > using MinHeap = priority_queue, Compare>; inline void input() {} template inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline istream& operator>>(istream &is, Container &vs) { for (auto &v: vs) is >> v; return is; } template inline istream& operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } inline void output() { cout << "\n"; } template inline void output(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << " "; output(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream &os, const Container &vs) { static constexpr const char *delim[] = {" ", ""}; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template inline vector makeVector(const T &init_value, size_t sz) { return vector(sz, init_value); } template inline auto makeVector(const T &init_value, size_t sz, Args... args) { return vector(init_value, args...))>(sz, makeVector(init_value, args...)); } template class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward(args)...); } }; template static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint{forward(f)}; } template struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template auto reversed(Container &c) { return reverse_t(c); } template inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } void operator|=(vector::reference lhs, const bool rhs) { lhs = lhs | rhs; } void ioinit() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); clog << fixed << setprecision(10); } // }}} End Header // SmartSieve {{{ class SmartSieve { intmax_t L, R, M; vector small; // 小さい篩 [2, sqrt(R)) vector> large; // 大きい篩 [L, R) vector aux; // aux[i] := large[i] の素因数の積 public: SmartSieve(intmax_t L, intmax_t R) : L(L), R(R), M(sqrt(R) + 1) { small.resize(M); iota(small.begin(), small.end(), 0); large.resize(R - L); aux.assign(R - L, 1); for (intmax_t i = 2; i * i < R; ++i) { if (small[i] < i) continue; for (intmax_t j = i * i; j < M; j += i) { if (small[j] == j) small[j] = i; } for (intmax_t j = (L + i - 1) / i * i; j < R; j += i) { intmax_t k = j; do { if (aux[j - L] * aux[j - L] > R) break; large[j - L].emplace_back(i); aux[j - L] *= i; k /= i; } while (k % i == 0); } } } bool isPrime(intmax_t n) const { assert(L <= n && n < R); if (n < M) return (2 <= n && small[n] == n); return (aux[n - L] == 1); } map primeFactor(intmax_t n) { assert(L <= n && n < R); map ret; for (const auto& e: large[n - L]) ret[e]++; n /= aux[n - L]; if (n >= M) { ret[n]++; return ret; } while (n > 1) { ret[small[n]]++; n /= small[n]; } return ret; } }; // }}} // ModInt {{{ template class ModInt { public: using value_type = intmax_t; private: static constexpr value_type cmod = Modulo; // compile-time static value_type rmod; // runtime value_type value = 0; static constexpr value_type inverse(value_type n, value_type m) { value_type a = n; value_type b = m; value_type x = 0; value_type y = 1; for (value_type u = y, v = x; a;) { const value_type t = b / a; swap(x -= t * u, u); swap(y -= t * v, v); swap(b -= t * a, a); } if ((x %= m) < 0) x += m; return x; } static value_type normalize(intmax_t n, value_type m) { if (n >= m) { n %= m; } else if (n < 0) { if ((n %= m) < 0) n += m; } return n; } public: ModInt() = default; ModInt(intmax_t n) : value(normalize(n, getModulo())) {} template constexpr explicit operator T() const { return static_cast(value); } ModInt& operator=(intmax_t n) { value = normalize(n, getModulo()); return *this; } ModInt& operator+=(const ModInt& other) { if ((value += other.value) >= getModulo()) value -= getModulo(); return *this; } ModInt& operator-=(const ModInt& other) { if ((value -= other.value) < 0) value += getModulo(); return *this; } ModInt& operator*=(const ModInt& other) { value = (value * other.value) % getModulo(); return *this; } ModInt& operator/=(const ModInt& other) { value = (value * inverse(other.value, getModulo())) % getModulo(); return *this; } ModInt& operator++() { if (++value == getModulo()) value = 0; return *this; } ModInt& operator--() { if (value-- == 0) value = getModulo() - 1; return *this; } ModInt operator++(int) { const ModInt tmp(*this); ++*this; return tmp; } ModInt operator--(int) { const ModInt tmp(*this); --*this; return tmp; } friend ModInt operator+(ModInt lhs, const ModInt& rhs) { return lhs += rhs; } friend ModInt operator-(ModInt lhs, const ModInt& rhs) { return lhs -= rhs; } friend ModInt operator*(ModInt lhs, const ModInt& rhs) { return lhs *= rhs; } friend ModInt operator/(ModInt lhs, const ModInt& rhs) { return lhs /= rhs; } ModInt operator+() const { return *this; } ModInt operator-() const { if (value == 0) return *this; return ModInt(getModulo() - value); } friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs.value == rhs.value; } friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return !(lhs == rhs); } friend ostream& operator<<(ostream& os, const ModInt& n) { return os << n.value; } friend istream& operator>>(istream& is, ModInt& n) { is >> n.value; n.value = normalize(n.value, getModulo()); return is; } static value_type getModulo() { return ((cmod > 0) ? cmod : rmod); } template ::type> static T setModulo(value_type m) { rmod = m; } }; template constexpr typename ModInt::value_type ModInt::cmod; template typename ModInt::value_type ModInt::rmod; // }}} // constexpr intmax_t MOD = intmax_t(1e9) + 7; constexpr intmax_t MOD = 998244353; using Mint = ModInt; vector sieve(intmax_t MAX) { vector is_prime(MAX + 1, true); is_prime[0] = is_prime[1] = false; for (intmax_t i = 2; i * i <= MAX; ++i) { if (is_prime[i]) { for (intmax_t j = 2; i * j <= MAX; ++j) { is_prime[i * j] = false; } } } return is_prime; } template T power(const T& b, const intmax_t& e) { T ret = 1; T n = b; for (intmax_t p = abs(e); p > 0; p >>= 1) { if (p & 1) ret *= n; n *= n; } if (e < 0) return T(1) / ret; return ret; } int main() { ioinit(); var(intmax_t, N); auto prime = sieve(N + 1); intmax_t mxp; repr(i, N, 1) { if (prime[i]) { mxp = i; break; } } SmartSieve sieve(1, N + 1); vector mxl(N + 1); // mxl[p] := mxp より小さい整数について、素因数 p の個数の max vector mxr(N + 1); // mxr[p] := mxp より大きい整数について、素因数 p の個数の max rep(i, 1, mxp) { for (const auto [p, c]: sieve.primeFactor(i)) { chmax(mxl[p], c); } } repc(i, mxp + 1, N) { for (const auto [p, c]: sieve.primeFactor(i)) { chmax(mxr[p], c); } } Mint res = 1; repc(i, 1, N) { res *= power(i, max(mxl[i], mxr[i])); } output(res); return 0; }