Problem H
Divide To The Basics
Filippo is very happy today: his math teacher just taught him about integer division!
What he learnt can be summed up in two statements:
-
An integer $A$ can be divided by integer $B$ only if $A \mod B = 0$, meaning that there is an integer $C$ such that $B \times C = A$
-
$1$ is a special number: not only it cannot be divided by any other value, but it doesn’t produce any change when used as a divisor - so Filippo decided he is not interested in division by $1$.
Filippo is still confused about these complex rules, so he’s trying to come up with a game to have fun with while learning: he starts with an integer $N$ and reduces it to $1$, applying a sequence of divisions to it. As he doesn’t like it, division by $1$ is not allowed.
He noticed that for some numbers, there are many different ways in which he can choose the sequence of divisors to use, but can’t quite figure out how many there are. Can you help him count them, for a given integer $N$?
As the answer can be quite large, output it modulo $10^9 + 7$.
Input
The first and only line contains one integer, $N$, the integer Filippo wants to reduce to one.
Output
You need to write a single line containing a single integer: the number of possible sequences of divisors to reduce $N$ to $1$, modulo $1000000007$.
Constraints
-
$1 \le N \le 10^{12}$.
Example
In the first example below, there’s $4$ different ways to reduce $8$:
-
$8 \div 8 = 1$
-
$8 \div 4 \div 2 = 1$
-
$8 \div 2 \div 4 = 1$
-
$8 \div 2 \div 2 \div 2 = 1$
| Sample Input 1 | Sample Output 1 |
|---|---|
8 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10000000000 |
145895908 |
