#include using namespace std; typedef long long ll; // Fast Factorization // https://judge.yosupo.jp/submission/38126 // !!! CHANGED THE PRIMARY TEST !!! typedef unsigned int uint; struct Mint { uint64_t n; static uint64_t mod, inv, r2; Mint() : n(0) { } Mint(const uint64_t &x) : n(init(x)) { } static uint64_t init(const uint64_t &w) { return reduce(__uint128_t(w) * r2); } static void set_mod(const uint64_t &m) { mod = inv = m; for(int i = 0; i < 5; i++) inv *= 2 - inv * m; r2 = -__uint128_t(m) % m; } static uint64_t reduce(const __uint128_t &x) { uint64_t y = uint64_t(x >> 64) - uint64_t((__uint128_t(uint64_t(x) * inv) * mod) >> 64); return int64_t(y) < 0 ? y + mod : y; } Mint& operator+= (const Mint &x) { n += x.n - mod; if(int64_t(n) < 0) n += mod; return *this; } Mint& operator+ (const Mint &x) const { return Mint(*this) += x; } Mint& operator*= (const Mint &x) { n = reduce(__uint128_t(n) * x.n); return *this; } Mint& operator* (const Mint &x) const { return Mint(*this) *= x; } uint64_t val() const { return reduce(n); } }; uint64_t Mint::mod, Mint::inv, Mint::r2; bool suspect(const uint64_t &a, const uint64_t &s, uint64_t d, const uint64_t &n) { if(Mint::mod != n) Mint::set_mod(n); Mint x(1), xx(a), o(x), m(n - 1); while(d > 0) { if(d & 1) x *= xx; xx *= xx; d >>= 1; } if(x.n == o.n) return true; for(uint r = 0; r < s; r++) { if(x.n == m.n) return true; x *= x; } return false; } bool is_prime(const uint64_t &n) { if(n <= 1 || (n > 2 && (~n & 1))) return false; uint64_t d = n - 1, s = 0; while(~d & 1) s++, d >>= 1; static const uint64_t a_big[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; static const uint64_t a_smo[] = {2, 7, 61}; if(n < 4759123141LL) { for(auto &&p : a_smo) { if(p >= n) break; if(!suspect(p, s, d, n)) return false; } } else { for(auto &&p : a_big) { if(p >= n) break; if(!suspect(p, s, d, n)) return false; } } return true; } uint64_t rho_pollard(const uint64_t &n) { if(~n & 1) return 2u; static random_device rng; uniform_int_distribution rr(1, n - 1); if(Mint::mod != n) Mint::set_mod(n); for(;;) { uint64_t c_ = rr(rng), g = 1, r = 1, m = 500; Mint y(rr(rng)), xx(0), c(c_), ys(0), q(1); while(g == 1) { xx.n = y.n; for(uint i = 1; i <= r; i++) y *= y, y += c; uint64_t k = 0; g = 1; while(k < r && g == 1) { for(uint i = 1; i <= (m > (r - k) ? (r - k) : m); i++) { ys.n = y.n; y *= y; y += c; uint64_t xxx = xx.val(), yyy = y.val(); q *= Mint(xxx > yyy ? xxx - yyy : yyy - xxx); } g = __gcd(q.val(), n); k += m; } r *= 2; } if(g == n) g = 1; while(g == 1) { ys *= ys; ys += c; uint64_t xxx = xx.val(), yyy = ys.val(); g = __gcd(xxx > yyy ? xxx - yyy : yyy - xxx, n); } if(g != n && is_prime(g)) return g; } assert(69 == 420); } template vector inter_factor(const T &n) { if(n < 2) return { }; if(is_prime(n)) return {n}; T d = rho_pollard(static_cast(n)); vector l = inter_factor(d), r = inter_factor(n / d); l.insert(l.end(), r.begin(), r.end()); return l; } template vector factor(T n) { vector f1; for(uint i = 2; i < 100; i += (i & 1) + 1) while(n % i == 0) f1.push_back(i), n /= i; vector f2 = inter_factor(n); f1.insert(f1.end(), f2.begin(), f2.end()); sort(f1.begin(), f1.end()); return f1; } template vector> makediv(T n) { vector pf = factor(n); vector> cmp; assert(n >= 2); T memo = pf[0]; int tmp = 0; for (int i=0; i<(int)pf.size(); i++){ if (memo == pf[i]){ tmp++; }else{ cmp.push_back(pair(memo, tmp)); memo = pf[i]; tmp = 1; } } cmp.push_back(pair(memo, tmp)); vector> ret(61,vector(0)); vector tar(61); auto calc = [&](auto self, T i, int s, int r, bool use) -> void { if (use){ if (r >= 1){ for (int j=1; j<=60; j++){ if (r % j != 0) tar[j]++; } } for (int j=0; j<61; j++){ if (tar[j] >= 1) continue; ret[j].push_back(i); } if (r >= 1){ for (int j=1; j<=60; j++){ if (r % j != 0) tar[j]--; } } } if (s >= (int)cmp.size()) return; if (r + 1 <= cmp[s].second){ self(self, i * cmp[s].first, s, r + 1, 1); } if (r >= 1){ for (int j=1; j<=60; j++){ if (r % j != 0) tar[j]++; } } self(self, i, s + 1, 0, 0); if (r >= 1){ for (int j=1; j<=60; j++){ if (r % j != 0) tar[j]--; } } return; }; calc(calc, 1, 0, 0, 1); for (int i=0; i<=60; i++){ sort(ret[i].begin(), ret[i].end()); } return ret; } int main(){ ll n; cin >> n; vector> d = makediv(n); auto calc = [&](auto self, ll i, int weight, bool start) -> ll { if (n % i != 0) return 0; if (weight == 1){ return 1LL; } ll ret = 0; for (ll x: d[weight]){ if ((__int128)i * x > n) break; if (start && x == 1) continue; ret += self(self, i * x, weight - 1, false); } return ret; }; ll ans = 0; for (int x=1; x<61; x++){ ans += calc(calc, 1LL, x, true); } cout << ans << '\n'; }