#include #pragma GCC optimize("O3") #pragma GCC target("sse4") using namespace std; using ll = long long; static constexpr ll Q = 998244353; template using Map = unordered_map; template vector factorize(Int n, Int i=1) { vector f; f.reserve( sqrt(n) ); for (; i*i < n; ++i) if (n % i == 0) f.push_back(i); i -= (i - (n / i) == 1); for (; i >= 1; i--) if (n % i == 0) f.push_back(n/i); return f; } struct sieve { static constexpr size_t N = 1000001; int spf[N] = {}; sieve() { spf[0] = spf[1] = -1; for (int i = 3; i <= N; i += 2) spf[i] = i; for (int i = 2; i <= N; i += 2) spf[i] = 2; // avoid lots of % later for (int i = 3; i*i <= N; i += 2) { if (spf[i] != i) continue; for (int j = i*i; j <= N; j += i) if (spf[j] == j) spf[j] = i; } } inline bool operator()(int n) { return spf[n] == n; } template inline Map factors(Int n) { Map mp; while (n != 1) { int p = spf[n]; while (n % p == 0) { ++mp[p]; n /= p; } } return mp; } } prime; int z{-1}; ll primes[78498]; signed main() { ll N; cin >> N; unordered_map dp; dp[1] = 1; auto facts = factorize(N); int X = facts.size(); // dp[x] = sum(dp[y]*Z forall y such that x%y==0) where Z is # of z s.t. lcm(y,z) = x for (int i = 2; i < sieve::N; ++i) if (prime(i)) primes[++z] = i; vector> prime_facs(X); for (int i = 0; i < X; ++i) { ll x = facts[i]; if (x < sieve::N) prime_facs[i] = prime.factors(x); else { ll y = x; for (int j = 0; j < 78498; ++j) { int p = primes[j]; while (y % p == 0) { y /= p; ++prime_facs[i][p]; } if (y == 1) break; } if (y != 1) prime_facs[i][y] = 1; } } for (int i = 1; i < X; ++i) { ll x = facts[i]; auto& pfx = prime_facs[i]; for (int j = 0; j < i; ++j) { ll y = facts[j]; if (x % y != 0) continue; ll ways = dp[y]; // # of z where lcm(y,z) = x auto& pfy = prime_facs[j]; for (auto [p, cnt] : pfx) if (pfy[p] == cnt) ways = ways * (cnt+1) % Q; dp[x] = (dp[x]+ways) % Q; } } cout << dp[N] << '\n'; }