#include 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 _big_prime_factorization { static uint64_t random_address() { char *p = new char; delete p; return uint64_t(p); } inline static auto rng = mt19937_64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)); struct barrett_reduction { unsigned mod; uint64_t div; barrett_reduction(unsigned m) : mod(m), div(-1LLU / m) {} unsigned operator()(uint64_t a) const { #ifdef __SIZEOF_INT128__ uint64_t q = uint64_t(__uint128_t(div) * a >> 64); uint64_t r = a - q * mod; return unsigned(r < mod ? r : r - mod); #endif return unsigned(a % mod); } }; static bool miller_rabin(unsigned n) { if (n < 2) return false; for (unsigned p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) if (n % p == 0) return n == p; auto get_miller_rabin_bases = [&]() -> vector { if (n < 341531) return {9345883071009581737LLU}; if (n < 1050535501) return {336781006125, 9639812373923155}; return {4230279247111683200, 14694767155120705706LLU, 16641139526367750375LLU}; }; int r = __builtin_ctz(n - 1); unsigned d = (n - 1) >> r; barrett_reduction barrett(n); auto mod_pow = [&](unsigned a, unsigned b) -> unsigned { unsigned result = 1; while (b > 0) { if (b & 1) result = barrett(uint64_t(result) * a); a = barrett(uint64_t(a) * a); b >>= 1; } return result; }; for (uint64_t a : get_miller_rabin_bases()) { if (a % n == 0) continue; unsigned x = mod_pow(unsigned(a % n), d); if (x == 1 || x == n - 1) continue; for (int i = 0; i < r - 1 && x != n - 1; i++) x = barrett(uint64_t(x) * x); if (x != n - 1) return false; } return true; } unsigned binary_gcd(uint64_t a, uint64_t b) { if (a == 0 || b == 0) return a + b; int common = __builtin_ctzll(a | b); b >>= __builtin_ctzll(b); do { a >>= __builtin_ctzll(a); if (a < b) swap(a, b); a -= b; } while (a != 0); return b << common; } unsigned pollard_rho(uint64_t n) { for (unsigned p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) if (n % p == 0) return p; barrett_reduction barrett(n); unsigned increment; auto g = [&](uint64_t x) -> unsigned { return barrett(x * x + increment); }; // Choose a jump size much larger than log(n) but much smaller than n^(1/4). int jump = (int64_t)(sqrt(log(n) * sqrt(sqrt(n)))); while (true) { increment = unsigned(rng() % n); unsigned start = unsigned(rng() % n); unsigned x = start, y = start, p = 1; vector products(jump + 1); do { // https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants products[0] = 1; for (int i = 1; i <= jump; i++) { x = g(x); y = g(g(y)); products[i] = barrett(uint64_t(products[i - 1]) * (max(x, y) - min(x, y))); } } while ((p = binary_gcd(products[jump], n)) == 1); if (p == n) { assert(products[jump] == 0); int index = jump; while (index > 0 && products[index] == 0) --index; p = binary_gcd(products[index], n); } if (p != 1 && p != n) return p; } } template Map operator()(T n) { if (n == 1) return {}; if (miller_rabin(n)) return {{n, 1}}; T x = pollard_rho(n); Map A = this->operator()(x), B = this->operator()(n / x); if (A.size() < B.size()) swap(A, B); for (auto [p, cnt] : B) A[p] += cnt; return A; } } prime_factors; 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 vector> prime_facs(X); for (int i = 0; i < X; ++i) prime_facs[i] = prime_factors(facts[i]); auto get = [] (Map& mp, ll key) { return mp.contains(key) ? mp[key] : 0; }; 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 (get(pfy, p) == cnt) ways = ways * (cnt+1) % Q; dp[x] = (dp[x]+ways) % Q; } } cout << dp[N] << '\n'; }