#include #include using namespace atcoder; using mint=modint998244353; using namespace std; using ll=long long; using ul=unsigned long long; int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}; int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1}; using Graph=vector>; template T pow_mod(T A, T N, T M) { T res = 1 % M; A %= M; while (N) { if (N & 1) res = (res * A) % M; A = (A * A) % M; N >>= 1; } return res; } bool is_prime(long long N) { if (N <= 1) return false; if (N == 2 || N == 3) return true; if (N % 2 == 0) return false; vector A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; long long s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : A) { if (a % N == 0) return true; long long t, x = pow_mod<__int128_t>(a, d, N); if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = __int128_t(x) * x % N; } if (t == s) return false; } } return true; } long long pollard(long long N) { if (N % 2 == 0) return 2; if (is_prime(N)) return N; long long step = 0; auto f = [&](long long x) -> long long { return (__int128_t(x) * x + step) % N; }; while (true) { ++step; long long x = 1, y = f(x); while (true) { long long p = gcd(y - x + N, N); if (p == 0 || p == N) break; if (p != 1) return p; x = f(x); y = f(f(y)); } } } ll paw(ll a,ll b){ ll t=a; ll ans=1; for(int i=0;i prime_factorize(long long N) { if (N == 1) return {}; long long p = pollard(N); if (p == N) return {p}; vector left = prime_factorize(p); vector right = prime_factorize(N / p); left.insert(left.end(), right.begin(), right.end()); sort(left.begin(), left.end()); return left; } int main(){ ll N; cin>>N; mapmp; vectorT=prime_factorize(N); for(auto a:T)mp[a]++; ll c=1; for(auto[k,v]:mp)c*=(pow(k,v+1)-1)/(k-1); cout<