#pragma GCC optimize("O2") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define int ll #define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1) #define INT128_MIN (-INT128_MAX - 1) #define clock chrono::steady_clock::now().time_since_epoch().count() #ifdef DEBUG #define dbg(x) cout << (#x) << " = " << (x) << '\n' #else #define dbg(x) #endif using namespace std; template, class OP = plus> void pSum(rng &&v) { if (!v.empty()) for(T p = v[0]; T &x : v | views::drop(1)) x = p = OP()(p, x); } template, class OP> void pSum(rng &&v, OP op) { if (!v.empty()) for(T p = v[0]; T &x : v | views::drop(1)) x = p = op(p, x); } template T floorDiv(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? a / b : (a - b + 1) / b; } template T ceilDiv(T a, T b) { if (b < 0) a *= -1, b *= -1; return a >= 0 ? (a + b - 1) / b : a / b; } template ostream& operator<<(ostream& os, const pair pr) { return os << pr.first << ' ' << pr.second; } template ostream& operator<<(ostream& os, const array &arr) { for(const T &X : arr) os << X << ' '; return os; } template ostream& operator<<(ostream& os, const vector &vec) { for(const T &X : vec) os << X << ' '; return os; } template ostream& operator<<(ostream& os, const set &s) { for(const T &x : s) os << x << ' '; return os; } #define rep(i, a, b) for (int i = int(a); i < int(b); i++) #define trav(a, x) for (auto& a : x) #define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--) #define all(x) x.begin(), x.end() template int sz(T&& a) { return int(size(forward(a))); } template using vc = vector; template using vvc = vc>; using ll = int64_t; using vi = vc; using pii = pair; using uint = uint32_t; using ull = uint64_t; mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); template struct ycr { F f; template explicit ycr(T&& f_) : f(forward(f_)) {} template decltype(auto) operator()(Args&&... args) { return f(ref(*this), forward(args)...); } }; template decltype(auto) yc(F&& f) { return ycr>(forward(f)); } // Reference: https://judge.yosupo.jp/submission/110118 struct montgomery { using T = ull; using u128 = __uint128_t; T n, n2, r, t, e; montgomery(T n_) : n(n_) { assert(n < (T(1) << 62)); assert(n % 2 == 1); n2 = n * 2; r = n & 3; rep(_,0,5) r *= 2-n*r; r = -r; assert(r * n == T(-1)); t = -T(n) % n; e = T(-u128(n) % n); } T reduce(u128 a) const { return T((a + u128(T(a) * r) * n) >> 64); } T mult(T a, T b) const { return reduce(u128(a) * b); } T encode(T a) const { return mult(a, e); } T decode(T a) const { a = reduce(a); return a < n ? a : a-n; } T pow(T a, ll b) const { assert(b >= 0); T v = t; while (b) { if (b & 1) v = mult(v, a); a = mult(a, a); b >>= 1; } return v; } bool is_prime() const { assert(n >= 3); assert(n & 1); T d = n-1; int s = __builtin_ctzll(d); d >>= s; auto check = [&](T a) -> int { a %= n; if (a == 0) return 1; T p = pow(encode(a), d); if (decode(p) == 1 || decode(p) == n-1) return 0; for (int z = 0; z < s; z++) { p = mult(p, p); if (decode(p) == n-1) return 0; } return -1; }; for (T a : {2,325,9375,28178,450775,9780504,1795265022}) { int w = check(a); if (w) return w == 1; } return true; } ull pollard() const { assert(n >= 3); assert(n & 1); if (is_prime()) return n; while (true) { T c = mt() % (n-1) + 1; T y = mt() % (n-1) + 1; auto f = [&](T a) -> T { return reduce(u128(a) * a + c); }; for (T s = 1; ; s *= 2) { T x = n2-y; T m = min(T(1) << (__lg(n)/6), s); rep(i,0,s/m) { T w = t, z = y; rep(j,0,m) { y = f(y); w = mult(w, y+x); } T g = __gcd(decode(w), n); if (g != 1) { if (g < n) return g; rep(j,0,m) { z = f(z); if ((g = __gcd(decode(z+x), n)) != 1) { if (g < n) return g; goto fail; } } assert(false); } } } fail:; } } }; using ull = uint64_t; bool is_prime(ull n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; return montgomery(n).is_prime(); } ull get_divisor(ull n) { assert(n > 1); if (n % 2 == 0) return 2; return montgomery(n).pollard(); } vc factorize(ull n) { vc res; yc([&](auto self, ull v) -> void { if (v == 1) return; ull d = get_divisor(v); if (d == v) { res.push_back(d); return; } self(d); self(v/d); })(n); return res; } signed main() { ios::sync_with_stdio(false), cin.tie(NULL); ull n; cin >> n; map m; for(auto x : factorize(n)) m[x]++; int mxL = 0; for(auto [_, f] : m) mxL = max(mxL, f); int ans = 0; for(int l = 1; l <= mxL; l++) { array cnt = {1, 0}; for(auto [_, f] : m) { vector dp(l + 1, vector(2, vector(f + 1))); dp[0][0][f] = cnt[0], dp[0][1][f] = cnt[1]; for(int i = 0; i < l; i++) for(int j : {0, 1}) for(int k = 0; k <= f; k++) { for(int r = 0; k - r * (i + 1) >= 0; r++) dp[i + 1][j | (r != 0 and i + 1 == l)][k - r * (i + 1)] += dp[i][j][k]; } cnt[0] = dp[l][0][0], cnt[1] = dp[l][1][0]; } ans += cnt[1]; } cout << ans << '\n'; return 0; }