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