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$.

Input

The first line contains one integer $n(1\le n\le 10^{15})$. $n$ will have at most $6$ distinct prime divisors.

Output

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$.