<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

497. Abelian Groups
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Andrew has just made a breakthrough in group theory: he realized that he can classify all finite Abelian groups (not much of a breakthrough, indeed). Given n, how many Abelian groups with n elements exist up to isomorphism? To help you solve this problem we provide some definitions and theorems from basic algebra (most are cited from Wikipedia). An abelian group is a set, A, together with an operation '·' that combines any two elements a and b to form another element denoted a · b. The symbol '·' is a general placeholder for a concretely given operation. To qualify as an abelian group, the set and operation, (A, ·), must satisfy five requirements known as the abelian group axioms:
Closure: for all a, b in A, the result of the operation a · b is also in A.
Associativity: for all a, b and c in A, the equation (a · b) · c = a · (b · c) holds.
Identity element: there exists an element e in A, such that for all elements a in A, the equation e · a = a · e = a holds.
Inverse element: for each a in A, there exists an element b in A such that a · b = b · a = e, where e is the identity element.
Commutativity: for all a, b in A, a · b = b · a.
An example of an abelian group is a cyclic group of order n: the set is integers between 0 and n-1, and the operation is sum modulo n. Given two abelian groups G and H, their direct sum is a group where each element is a pair (g, h) with g from G and h from H, and operations are performed on each element of the pair independently. Two groups G and H are isomorphic when there exists a one-to-one mapping f from elements of G to elements of H such that f(a) · f(b) = f(a · b) for all a and b. The fundamental theorem of finite abelian groups states that every finite abelian group is isomorphic to a direct sum of several cyclic groups. The Chinese remainder theorem states that when m and n are coprime, a cyclic group of order mn is isomorphic to the direct sum of the cyclic group of order m and the cyclic group of order n.
Input
First and only line of the input file contains an integer n, 1 ≤ n ≤ 1012.
Output
In the only line of the output file write the number of abelian groups with n elements.
Example(s)
sample input
sample output
5
1

sample input
sample output
4
2

sample input
sample output
12
2

<|response|>
1. Abridged problem statement  
Given an integer n (1 ≤ n ≤ 10^12), compute the number of non-isomorphic finite abelian groups of order n.

2. Key observations  
- By the Fundamental Theorem of Finite Abelian Groups, every finite abelian group of order n factors uniquely (up to isomorphism) as a direct sum of p-power cyclic groups, one p-group for each prime p dividing n.  
- All choices for different primes are independent, so the total count is the product over primes p|n of the number of abelian p-groups of order p^e.  
- The number of abelian p-groups of order p^e equals the partition function p(e), i.e. the number of ways to write e as a sum of positive integers in nonincreasing order.  
- Thus if n = ∏ p_i^{e_i}, the answer is ∏ p(e_i).

3. Full solution approach  
a. Factor n by trial division up to √n to find each prime exponent e_i.  
b. Let E be the maximum exponent among the e_i. Precompute partition numbers p(0..E) using Euler’s pentagonal recurrence:  
   p(0)=1; for m>0,  
     p(m) = ∑_{k=1..∞} (−1)^{k−1} [p(m − k(3k−1)/2) + p(m − k(3k+1)/2)]  
   stopping when arguments go negative. This runs in O(E √E).  
c. Initialize answer = 1. For each exponent e_i multiply answer by p(e_i).  
d. Output the final product.

4. C++ implementation with detailed comments  
    #include <bits/stdc++.h>
    using namespace std;

    // Compute partition numbers p(0..max_n) via Euler's pentagonal recurrence
    vector<long long> compute_partitions(int max_n) {
        vector<long long> p(max_n + 1, 0);
        p[0] = 1;  // By definition, there is 1 way to partition 0.
        // Fill p[1..max_n]
        for (int m = 1; m <= max_n; ++m) {
            long long sum = 0;
            // Generate generalized pentagonal numbers until they exceed m
            for (int k = 1; ; ++k) {
                int pent1 = k * (3*k - 1) / 2;     // k(3k−1)/2
                int pent2 = k * (3*k + 1) / 2;     // k(3k+1)/2
                if (pent1 > m && pent2 > m) break;
                // Sign pattern: +, +, −, −, +, +, ...
                int sign = (k & 1) ? +1 : -1;
                if (pent1 <= m) sum += sign * p[m - pent1];
                if (pent2 <= m) sum += sign * p[m - pent2];
            }
            p[m] = sum;
        }
        return p;
    }

    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        long long n;
        cin >> n;

        // Factor n by trial division and collect exponents
        long long temp = n;
        vector<int> exponents;
        for (long long d = 2; d * d <= temp; ++d) {
            if (temp % d == 0) {
                int cnt = 0;
                while (temp % d == 0) {
                    temp /= d;
                    ++cnt;
                }
                exponents.push_back(cnt);
            }
        }
        if (temp > 1) {
            // Remaining factor is prime
            exponents.push_back(1);
        }

        // Determine max exponent to know how far to compute partitions
        int max_e = 0;
        for (int e : exponents) if (e > max_e) max_e = e;

        // Precompute partition numbers up to max_e
        vector<long long> part = compute_partitions(max_e);

        // Multiply partition(e) for each prime exponent e
        long long answer = 1;
        for (int e : exponents) {
            answer *= part[e];
        }

        cout << answer << "\n";
        return 0;
    }

5. Python implementation with detailed comments  
    import sys

    # Compute partition numbers p[0..max_n] using Euler's pentagonal recurrence
    def compute_partitions(max_n):
        p = [0] * (max_n + 1)
        p[0] = 1  # base case
        for m in range(1, max_n + 1):
            total = 0
            k = 1
            while True:
                pent1 = k * (3*k - 1) // 2
                pent2 = k * (3*k + 1) // 2
                if pent1 > m and pent2 > m:
                    break
                sign = 1 if (k & 1) else -1
                if pent1 <= m:
                    total += sign * p[m - pent1]
                if pent2 <= m:
                    total += sign * p[m - pent2]
                k += 1
            p[m] = total
        return p

    def main():
        data = sys.stdin.read().strip().split()
        n = int(data[0])

        # Factor n by trial division
        temp = n
        exponents = []
        # Check factor 2
        cnt = 0
        while temp % 2 == 0:
            temp //= 2
            cnt += 1
        if cnt > 0:
            exponents.append(cnt)
        # Check odd divisors
        f = 3
        while f * f <= temp:
            cnt = 0
            while temp % f == 0:
                temp //= f
                cnt += 1
            if cnt > 0:
                exponents.append(cnt)
            f += 2
        # If a prime >1 remains
        if temp > 1:
            exponents.append(1)

        # Precompute partition numbers up to the largest exponent
        max_e = max(exponents, default=0)
        part = compute_partitions(max_e)

        # Multiply partition(e) for each exponent
        answer = 1
        for e in exponents:
            answer *= part[e]

        print(answer)

    if __name__ == "__main__":
        main()