<|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. Precompute partition numbers p(0..100) 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(100 √100).
   (The max exponent for n ≤ 10^12 is 39, since 2^40 > 10^12.)
c. Initialize answer = 1. For each exponent e_i multiply answer by p(e_i).
d. Output the final product.

4. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t n;

void read() { cin >> n; }

vector<int64_t> compute_partitions(int max_n) {
    vector<int64_t> p(max_n + 1, 0);
    p[0] = 1;

    for(int n = 1; n <= max_n; ++n) {
        int64_t sum = 0;
        int k = 1;
        while(true) {
            int pent1 = (k * (3 * k - 1)) / 2;
            int pent2 = ((-k) * (3 * (-k) - 1)) / 2;
            if(pent1 > n && pent2 > n) {
                break;
            }

            int sign = (k % 2 == 1) ? 1 : -1;
            if(pent1 <= n) {
                sum += sign * p[n - pent1];
            }

            if(pent2 <= n && pent2 != pent1) {
                sum += sign * p[n - pent2];
            }

            ++k;
        }

        p[n] = sum;
    }

    return p;
}

void solve() {
    // By the fundamental theorem of finite abelian groups and the Chinese
    // remainder theorem, the number of abelian groups of order n is
    // multiplicative over the prime factorization: for a prime power p^e the
    // count of distinct decompositions equals the number of integer partitions
    // of e. So factorize n, and multiply together the partition counts of each
    // exponent. compute_partitions uses Euler's pentagonal number recurrence to
    // build the partition function up to 100 (the max exponent for n <= 10^12
    // is 39, since 2^40 > 10^12). The leftover factor after trial division up
    // to sqrt(n) is a single prime with exponent 1, contributing p(1) = 1.

    vector<int64_t> partitions = compute_partitions(100);
    int64_t result = 1;
    for(int64_t p = 2; p * p <= n; ++p) {
        if(n % p == 0) {
            int e = 0;
            while(n % p == 0) {
                e++;
                n /= p;
            }

            result *= partitions[e];
        }
    }

    if(n > 1) {
        result *= partitions[1];
    }

    cout << result << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution

```python
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()
```
