Problems
Six
Six
Elly studies the properties of some given integer $n$. So far she has discovered that it has no more than six distinct prime divisors. A prime number (or a prime) is a natural number greater than $1$ that has no positive divisors other than $1$ and itself.
Now the girl spends her time in the following way. Starting with an empty list, she writes divisors of $n$, greater than $1$ (some divisors she may repeat several times). When adding a new number to the list, she makes sure that it has common divisors greater than $1$ with at most one of the already written numbers.
For example, if the number $n$ is $12156144$, some of the many possible valid sequences the girl can generate are $(42)$, $(616, 6, 91, 23)$, $(91, 616, 6, 23)$, $(66, 7)$, $(66, 7, 7, 23, 299, 66)$, $(143, 13, 66)$ и $(42, 12156144)$. Examples for invalid sequences would be $(5, 11)$, since $5$ is not a divisor of $12156144$, or $(66, 13, 143)$, since $143$ has common divisors with both $13$ and $66$.
Now Elly is wondering how many different valid sequences of divisors of $n$ exist. We consider two sequences different if they have different length or there is a position, in which they have different numbers.
Write a program that helps Elly to find the number of valid sequences of divisors of $n$.
\InputFile
The first line contains one integer $n~(1 \le n \le 10^{15})$. $n$ will have at most $6$ distinct prime divisors.
\OutputFile
Print one integer --- the number of different sequences of divisors of $n$, which could have been written by Elly. Since this number can be rather large, you are required to print only its remainder when divided by $10^9 + 7$.
\Examples
Explanation for the first test. All $28$ valid sequences are: $\{(2)$, $(2, 2)$, $(2, 2, 3)$, $(2, 2, 3, 3)$, $(2, 3)$, $(2, 3, 2)$, $(2, 3, 2, 3)$, $(2, 3, 3)$, $(2, 3, 3, 2)$, $(2, 6)$, $(2, 6, 3)$, $(3)$, $(3, 2)$, $(3, 2, 2)$, $(3, 2, 2, 3)$, $(3, 2, 3)$, $(3, 2, 3, 2)$, $(3, 3)$, $(3, 3, 2)$, $(3, 3, 2, 2)$, $(3, 6)$, $(3, 6, 2)$, $(6)$, $(6, 2)$, $(6, 2, 3)$, $(6, 3)$, $(6, 3, 2)$, $(6, 6)\}$.
Explanation for the fourth test. The answer is $14104757650$, but since you are required to print it modulo $10^9 + 7$, the actual result is $14104757650~\%~(10^9 + 7) = 104757552$.
Input example #1
6
Output example #1
28
Input example #2
203021
Output example #2
33628
Input example #3
60357056536
Output example #3
907882
Input example #4
12156144
Output example #4
104757552