// https://yukicoder.me/problems/no/2318 // use the trick from Hossam & trainees. // compute list of all primes up to sqrt(N) // use repeated division to find any remaining "big" primes #include #pragma GCC optimize("O3") #pragma GCC target("sse4") using namespace std; using ll = long long; static constexpr ll Q = 998244353; template using Map = 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; ll primes[78498]; // list of all primes < 1e6 Map prime_factorize(ll x) { if (x < sieve::N) return prime.factors(x); Map mp; ll y = x; for (int p : primes) { while (y % p == 0) { y /= p; ++mp[p]; } if (y == 1) break; } if (y != 1) mp[y] = 1; return mp; } signed main() { ll N; cin >> N; for (int z{-1}, i{2}; i <= (ll)sqrt(N); ++i) if ( prime(i) ) primes[++z] = i; unordered_map dp; // dp[x] = sum(dp[y]*Z forall y such that x%y==0) where Z is # of z s.t. lcm(y,z) = x dp[1] = 1; auto facts = factorize(N); int X = facts.size(); vector> prime_facs(X); for (int i = 0; i < X; ++i) { ll f = facts[i]; prime_facs[i] = prime_factorize(f); } 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'; }