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), and (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

From the first line of the standard input your program has to read one integer N (1 <= N <= 10¹⁵). In 100% of the tests N will have at most 6 distinct prime divisors.

Output

On the standard output your program has to 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⁹+7.

Constraints

Time limit: 2 seconds
Memory limit: 256 megabytes

Examples

input
6

output
28

input
203021

output
33628

input
60357056536

output
907882

input
12156144

output
104757552

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⁹+7, the actual result is 14104757650 % 1000000007 = 104757552