/* -*- coding: utf-8 -*- * * 1396.cc: No.1396 Giri - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_P = 1000000; const int MOD = 998244353; /* typedef */ typedef long long ll; /* global variables */ bool primes[MAX_P + 1]; int pnums[MAX_P], fs[MAX_P]; /* subroutines */ int gen_primes(int maxp, int pnums[]) { memset(primes, true, sizeof(primes)); primes[0] = primes[1] = false; int p, pn = 0; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums[pn++] = p; for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums[pn++] = p; return pn; } void prime_decomp(int n, int pn, int pnums[]) { for (int i = 0, pi; i < pn && (pi = pnums[i]) * pnums[i] <= n; i++) if (n % pi == 0) { int fi = 1; n /= pi; while (n % pi == 0) n /= pi, fi++; fs[i] = max(fs[i], fi); } if (n > 1) { int k = lower_bound(pnums, pnums + pn, n) - pnums; fs[k] = max(fs[k], 1); } } int powmod(int a, int n) { // a^n % MOD int pm = 1; while (n > 0) { if (n & 1) pm = (ll)pm * a % MOD; a = (ll)a * a % MOD; n >>= 1; } return pm; } /* main */ int main() { int pn = gen_primes(MAX_P, pnums); //printf("pn=%d\n", pn); int n; scanf("%d", &n); for (int i = 2; i <= n; i++) prime_decomp(i, pn, pnums); int maxpi = pn - 1; while (fs[maxpi] == 0) maxpi--; //printf("maxp=%d\n", pnums[maxpi]); int p = 1; for (int i = 0; i < maxpi; i++) if (fs[i] > 0) p = (ll)p * powmod(pnums[i], fs[i]) % MOD; printf("%d\n", p); return 0; }