/* -*- coding: utf-8 -*- * * 2318.cc: No.2318 Phys Bone Maker - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_P = 1000100; const int MOD = 998244353; /* typedef */ typedef long long ll; typedef vector vi; typedef vector vvi; typedef vector vl; /* global variables */ bool primes[MAX_P + 1]; /* subroutines */ int gen_primes(int maxp, vi &pnums) { fill(primes, primes + maxp + 1, true); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); return (int)pnums.size(); } bool prime_decomp(ll n, vi &pnums, vl &pv, vi &fv) { pv.clear(), fv.clear(); int pn = pnums.size(); for (int i = 0; i < pn; i++) { int pi = pnums[i]; if ((ll)pi * pi > n) { if (n > 1) pv.push_back(n), fv.push_back(1); return true; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; pv.push_back(pi), fv.push_back(fi); } } return false; } inline void addmod(int &a, int b) { a = (a + b) % MOD; } int divnum(vi &fv0, vi &fv1) { int p = 1; for (int i = 0; i < fv0.size(); i++) { if (fv0[i] > fv1[i]) return 0; if (fv0[i] == fv1[i]) p *= fv0[i] + 1; } return p; } /* main */ int main() { vi pnums; gen_primes(MAX_P, pnums); ll n; scanf("%lld", &n); vl pv; vi fv; prime_decomp(n, pnums, pv, fv); int l = pv.size(); vvi fvs; for (vi v(l, 0);;) { fvs.push_back(v); int i = 0; for (; i < l; i++) { if (++v[i] > fv[i]) v[i] = 0; else break; } if (i >= l) break; } int m = fvs.size(); //printf("m=%d\n", m); vi dp(m, 0); dp[0] = 1; for (int i = 0; i < m - 1; i++) for (int j = i + 1; j < m; j++) { int d = divnum(fvs[i], fvs[j]); if (d > 0) addmod(dp[j], (ll)dp[i] * d % MOD); } printf("%d\n", dp[m - 1]); return 0; }