#include #define ALL(x) std::begin(x), std::end(x) using namespace std; // @title mod int #include using ll = long long; // @title 素数判定、素因数分解 #include #include #include #include using ll = long long; class Prime { // n以下の素数を列挙する public: const int n; std::vector is_prime; std::vector primes; Prime(int size) : n(size), is_prime(n+1, true) { is_prime[0] = false; is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (!is_prime[i]) continue; primes.push_back(i); int tmp = 2*i; while (tmp <= n) { is_prime[tmp] = false; tmp += i; } } } bool check(int x) { return is_prime[x]; } }; struct PrimeFactorization { // n*n以下の数についての素因数分解 const int n; Prime p; PrimeFactorization(int n) : n(n), p(n) {} std::map calc(ll a) { std::map ret; ll tmp = a; for (int i: p.primes) { if (i > tmp) break; int count = 0; while (tmp % i == 0) { ++count; tmp /= i; } if (count > 0) ret[i] = count; } if (tmp > 1) ret[tmp] = 1; return ret; } }; struct FastPrimeFactorization { /** * @brief n以下の数について高速で、n*n以下の数で普通に素因数分解を行う * */ int n; std::vector divides; // その数を割り切る最小の素因数 std::vector primes; // n以下の素数 FastPrimeFactorization(int n) : n(n), divides(n+1) { assert(n <= 2000000); // エラトステネスの篩にかけ、最小の素因数をdividesに書き込んでいく for (int i = 2; i <= n; ++i) { if (divides[i] > 0) continue; primes.push_back(i); int j = i; while (j <= n) { if (divides[j] == 0) { divides[j] = i; } j += i; } } // for (int i = 0; i <= n; ++i) { // cout << i << " " << divides[i] << endl; // } } std::map calc(ll a) { std::map ret; // 高速に計算できない部分は愚直にやる ll tmp = a; for (int i: primes) { if (tmp <= n || i > tmp) break; int count = 0; while (tmp % i == 0) { ++count; tmp /= i; } if (count > 0) ret[i] = count; } if (tmp > n) { // nより大きい素数 ret[tmp] = 1; return ret; } while (tmp > 1) { int d = divides[tmp]; ++ret[d]; tmp /= d; } return ret; } }; #if 0 using namespace std; int main() { FastPrimeFactorization pf(1000000); // PrimeFactorization pf(1000000); std::map factors; ll a = (ll)2*2*5*7*7*41; factors = pf.calc(a); cout << "prime factors of " << a << " is ..." << endl; for (auto it : factors) { cout << it.first << " " << it.second << endl; } cout << endl; // 最大数付近での確認 a = (ll)999983*999983; factors = pf.calc(a); cout << "prime factors of " << a << " is ..." << endl; for (auto it : factors) { cout << it.first << " " << it.second << endl; } } #endif #ifdef MUTABLE int mod; #else template #endif struct ModInt { int val; ModInt inv() const{ int tmp,a=val,b=mod,x=1,y=0; while(b)tmp=a/b,a-=tmp*b,std::swap(a,b),x-=tmp*y,std::swap(x,y); return ModInt(x); } ModInt():val(0){} ModInt(ll x){if((val=x%mod)<0)val+=mod;} ModInt pow(ll t){ModInt res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;} ModInt& operator+=(const ModInt& x){if((val+=x.val)>=mod)val-=mod;return *this;} ModInt& operator-=(const ModInt& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;} ModInt& operator*=(const ModInt& x){val=(ll)val*x.val%mod; return *this;} ModInt& operator/=(const ModInt& x){return *this*=x.inv();} bool operator==(const ModInt& x) const{return val==x.val;} bool operator!=(const ModInt& x) const{return val!=x.val;} bool operator<(const ModInt& x) const{return val(const ModInt& x) const{return val>x.val;} bool operator>=(const ModInt& x) const{return val>=x.val;} ModInt operator+(const ModInt& x) const{return ModInt(*this)+=x;} ModInt operator-(const ModInt& x) const{return ModInt(*this)-=x;} ModInt operator*(const ModInt& x) const{return ModInt(*this)*=x;} ModInt operator/(const ModInt& x) const{return ModInt(*this)/=x;} friend std::ostream& operator<<(std::ostream& os, const ModInt& mi) { os << mi.val; return os; } static int get_mod() { return mod; } }; #ifndef MUTABLE using modint = ModInt<998244353>; #endif int main() { FastPrimeFactorization pf(1000001); int n; cin >> n; std::map all; modint ans = 1; ll m = 0; for (int i = 1; i <= n; ++i) { std::map factors = pf.calc(i); for (auto it: factors) { all[it.first] = max(all[it.first], it.second); m = max(m, it.first); } } for (auto it: all) { ans *= modint(it.first).pow(it.second); } ans /= m; cout << ans << endl; return 0; }