#if __has_include("all.hpp") #include "all.hpp" #else #include // #include #endif using ll = long long int; template bool chmin(T &x, const T val) { if (x > val) { x = val; return true; } else { return false; } } template bool chmax(T &x, const T val) { if (x < val) { x = val; return true; } else { return false; } } template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::istream &operator>>(std::istream &is, std::tuple &tpl) { std::apply([&](auto &&...args) { (is >> ... >> args); }, tpl); return is; } // template * = // nullptr> std::ostream &operator<<(std::ostream &os, const mint &v) { // return os << v.val(); // } // // template * = // nullptr> std::istream &operator>>(std::istream &is, mint &v) { // int tmp; // is >> tmp; // v = tmp; // return is; // } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &x : v) is >> x; return is; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (int i = 0; i < v.size(); i++) os << v[i] << (i == v.size() - 1 ? "" : " "); return os; } struct Initialization { Initialization() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } } initialization; constexpr std::pair dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; template using infs = std::numeric_limits; template class factorials { public: static size_t n; static std::vector fact, inv_fact; static void extend(size_t m) { if (m <= n) return; fact.resize(m + 1); inv_fact.resize(m + 1); for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i; inv_fact[m] = fact[m].inv(); for (size_t i = m; i > n + 1; i--) inv_fact[i - 1] = inv_fact[i] * i; n = m; } static T inv(int k) { extend(k); return inv_fact[k]; } static T get(int k) { extend(k); return fact[k]; } static T perm(int n, int k) { if (n < k) return 0; if (k < 0) return 0; extend(n); return fact[n] * inv_fact[n - k]; } static T choose(int n, int k) { if (n < k) return 0; if (k < 0) return 0; extend(n); return fact[n] * inv_fact[n - k] * inv_fact[k]; } }; template size_t factorials::n = 0; template std::vector factorials::fact = {1}; template std::vector factorials::inv_fact = {1}; // template // class fps { // std::vector v; // // public: // using value_type = T; // using reference = T &; // using const_reference = const T &; // using iterator = typename std::vector::iterator; // using const_iterator = typename std::vector::const_iterator; // // size_t size() const { return v.size(); } // // const std::vector &data() const { return v; } // // explicit fps(int n) : v(n) {} // // fps(const std::vector &v) : v(v) {} // fps(std::vector &&v) : v(v) {} // // template // fps(InputIterator first, InputIterator last) : v(first, last) {} // // fps(std::initializer_list init) : v(init) {} // // void resize(int n) { v.resize(n); } // // T &operator[](int i) { return v[i]; } // // iterator begin() { return v.begin(); } // // iterator end() { return v.end(); } // // fps take(int n) const { // return fps(v.begin(), v.begin() + std::min(n, (int)v.size())); // } // // fps diff() const { // std::vector res(v.size() - 1); // for (int i = 0; i < res.size(); i++) res[i] = v[i + 1] * (i + 1); // return fps(res); // } // // fps integral() const { // std::vector res(v.size() + 1); // for (int i = 0; i < v.size(); i++) res[i + 1] = v[i] / (i + 1); // return fps(res); // } // // fps inv(int deg = -1) const { // assert(v[0] != 0); // // if (deg == -1) deg = size(); // std::vector res(deg); // // res[0] = v[0].inv(); // // T inv4 = T(4).inv(), invd = inv4; // // for (int d = 1; d < deg; d <<= 1) { // std::vector f(2 * d), g(2 * d); // // std::copy(v.begin(), v.begin() + std::min(2 * d, (int)v.size()), // f.begin()); // std::copy(res.begin(), res.begin() + d, g.begin()); // // atcoder::internal::butterfly(f); // atcoder::internal::butterfly(g); // // for (int i = 0; i < 2 * d; i++) f[i] *= g[i]; // // atcoder::internal::butterfly_inv(f); // // for (int i = 0; i < d; i++) f[i] = 0; // // atcoder::internal::butterfly(f); // // for (int i = 0; i < 2 * d; i++) f[i] *= g[i]; // // atcoder::internal::butterfly_inv(f); // // for (int i = d; i < std::min(2 * d, deg); i++) res[i] = -f[i] * invd; // // invd *= inv4; // } // // return res; // } // // fps shift(T c) const { // std::vector res(size()), ifacts(size()); // // T x = 1; // // for (int i = 0; i < size(); i++) { // ifacts[i] = x * factorials::inv(i); // x *= c; // } // // for (int i = 0; i < size(); i++) { // res[size() - 1 - i] = v[i] * factorials::get(i); // } // // res = atcoder::convolution(res, ifacts); // // res.resize(size()); // // std::ranges::reverse(res); // // for (int i = 0; i < size(); i++) { // res[i] *= factorials::inv(i); // } // // return res; // } // // fps operator-() const { // fps res(v.size()); // for (int i = 0; i < v.size(); i++) res[i] = -v[i]; // return res; // } // // fps &operator+=(const fps &rhs) { // if (v.size() < rhs.v.size()) v.resize(rhs.v.size()); // for (int i = 0; i < rhs.v.size(); i++) v[i] += rhs.v[i]; // return *this; // } // // fps &operator-=(const fps &rhs) { // if (v.size() < rhs.v.size()) v.resize(rhs.v.size()); // for (int i = 0; i < rhs.v.size(); i++) v[i] -= rhs.v[i]; // return *this; // } // // fps &operator*=(const fps &rhs) { // return *this = atcoder::convolution(v, rhs.v); // } // // fps &operator/=(const fps &rhs) { return *this *= rhs.inv(); } // // fps &operator+=(const T &rhs) { // if (v.size() == 0) v.resize(1); // v[0] += rhs; // return *this; // } // // fps &operator-=(const T &rhs) { // if (v.size() == 0) v.resize(1); // v[0] -= rhs; // return *this; // } // // fps &operator*=(const T &rhs) { // for (int i = 0; i < v.size(); i++) v[i] *= rhs; // return *this; // } // // fps &operator/=(const T &rhs) { // T rhs_inv = rhs.inv(); // for (int i = 0; i < v.size(); i++) v[i] *= rhs_inv; // return *this; // } // // friend fps operator+(const fps &lhs, const fps &rhs) { // return fps(lhs) += rhs; // } // // friend fps operator-(const fps &lhs, const fps &rhs) { // return fps(lhs) -= rhs; // } // // friend fps operator*(const fps &lhs, const fps &rhs) { // return fps(lhs) *= rhs; // } // // friend fps operator/(const fps &lhs, const fps &rhs) { // return fps(lhs) /= rhs; // } // // friend fps operator+(const fps &lhs, const T &rhs) { return fps(lhs) += // rhs; } // // friend fps operator-(const fps &lhs, const T &rhs) { return fps(lhs) -= // rhs; } // // friend fps operator*(const fps &lhs, const T &rhs) { return fps(lhs) *= // rhs; } // // friend fps operator/(const fps &lhs, const T &rhs) { return fps(lhs) /= // rhs; } // // friend fps operator+(const T &lhs, const fps &rhs) { return fps(rhs) += // lhs; } // // friend fps operator-(const T &lhs, const fps &rhs) { // return -(fps(rhs) -= lhs); // } // // friend fps operator*(const T &lhs, const fps &rhs) { return fps(rhs) *= // lhs; } // }; // // template // T bostan_mori(int n, fps P, fps Q) { // assert(P.size() < Q.size()); // // P.resize(Q.size() - 1); // // while (n) { // fps qm = Q; // for (int i = 1; i < Q.size(); i += 2) qm[i] = -qm[i]; // // fps U = P * qm; // fps V = Q * qm; // // for (int i = n & 1; i < U.size(); i += 2) P[i / 2] = U[i]; // for (int i = 0; i < V.size(); i += 2) Q[i / 2] = V[i]; // // n /= 2; // } // // return P[0] / Q[0]; // } // using mint = atcoder::modint998244353; // using mint = atcoder::modint1000000007; // using fs = factorials; namespace ppppp { using namespace std; // montgomery modint (MOD < 2^62, MOD is odd) struct MontgomeryModInt64 { using mint = MontgomeryModInt64; using u64 = uint64_t; using u128 = __uint128_t; // static menber static u64 MOD; static u64 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2^64) static u64 T128; // 2^128 (mod MOD) // inner value u64 val; // constructor MontgomeryModInt64() : val(0) {} MontgomeryModInt64(long long v) : val(reduce((u128(v) + MOD) * T128)) {} u64 get() const { u64 res = reduce(val); return res >= MOD ? res - MOD : res; } // mod getter and setter static u64 get_mod() { return MOD; } static void set_mod(u64 mod) { assert(mod < (1LL << 62)); assert((mod & 1)); MOD = mod; T128 = -u128(mod) % mod; INV_MOD = get_inv_mod(); } static u64 get_inv_mod() { u64 res = MOD; for (int i = 0; i < 5; ++i) res *= 2 - MOD * res; return res; } static u64 reduce(const u128 &v) { return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64; } // arithmetic operators mint operator-() const { return mint() - mint(*this); } mint operator+(const mint &r) const { return mint(*this) += r; } mint operator-(const mint &r) const { return mint(*this) -= r; } mint operator*(const mint &r) const { return mint(*this) *= r; } mint operator/(const mint &r) const { return mint(*this) /= r; } mint &operator+=(const mint &r) { if ((val += r.val) >= 2 * MOD) val -= 2 * MOD; return *this; } mint &operator-=(const mint &r) { if ((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD; return *this; } mint &operator*=(const mint &r) { val = reduce(u128(val) * r.val); return *this; } mint &operator/=(const mint &r) { *this *= r.inv(); return *this; } mint inv() const { return pow(MOD - 2); } mint pow(u128 n) const { mint res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } // other operators bool operator==(const mint &r) const { return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val); } bool operator!=(const mint &r) const { return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val); } friend istream &operator>>(istream &is, mint &x) { long long t; is >> t; x = mint(t); return is; } friend ostream &operator<<(ostream &os, const mint &x) { return os << x.get(); } friend mint modpow(const mint &r, long long n) { return r.pow(n); } friend mint modinv(const mint &r) { return r.inv(); } }; typename MontgomeryModInt64::u64 MontgomeryModInt64::MOD, MontgomeryModInt64::INV_MOD, MontgomeryModInt64::T128; // Miller-Rabin bool MillerRabin(long long N, vector A) { using mint = MontgomeryModInt64; mint::set_mod(N); long long s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : A) { if (N <= a) return true; mint x = mint(a).pow(d); if (x != 1) { long long t; for (t = 0; t < s; ++t) { if (x == N - 1) break; x *= x; } if (t == s) return false; } } return true; } bool is_prime(long long N) { if (N <= 1) return false; else if (N == 2) return true; else if (N % 2 == 0) return false; else if (N < 4759123141LL) return MillerRabin(N, {2, 7, 61}); else return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } } // namespace ppppp int main() { ll N; std::cin >> N; if (ppppp::is_prime(N)) { std::cout << 1 << std::endl; return 0; } std::vector> ps; for (ll i = 2; i * i * i <= N; i++) { if (N % i == 0) { int cnt = 0; while (N % i == 0) { N /= i; cnt++; } ps.emplace_back(i, cnt); } } if (ps.empty()) { ll ok = 1000000000, ng = 0; while (ok - ng > 1) { ll mid = (ok + ng) / 2; if (mid * mid >= N) { ok = mid; } else { ng = mid; } } if (ok * ok == N) { std::cout << 2 << std::endl; } else { std::cout << 1 << std::endl; } return 0; } if (N > 1) { ps.emplace_back(N, 1); } std::vector nanachi; for (auto [p, c] : ps) { nanachi.push_back(c); } std::ranges::sort(nanachi, std::greater<>()); ll ans = 0; int M = nanachi[0]; std::vector dp(M + 1, std::vector(M + 1, -1)); auto rec = [&](auto rec, int k, int n) -> ll { if (k < 0 || n < 0) return 0; if (k > n) return 0; if (dp[k][n] != -1) return dp[k][n]; if (k == n) return 1; if (k == 0) return 0; return dp[k][n] = rec(rec, k, n - k) + rec(rec, k - 1, n - 1); }; std::vector p(M + 1, 1); for (int len = 2; len <= M; len++) { for (int i = len; i <= M; i++) { p[i] += rec(rec, len, i); } } ll tmp = 1; for (int i = 0; i < nanachi.size(); i++) { tmp *= p[nanachi[i]]; } ans += tmp; std::cout << ans << std::endl; }