Problem Description

Elly is studying some properties of a positive integer \( N \), and she has found that \( N \) has no more than 6 distinct prime factors.

Next, she generates a list in a specific manner, starting with an empty list. She writes down a divisor \( x \) of \( N \) that is greater than 1 and adds it to the list, ensuring that among all the numbers already in the list, there is no more than 1 number that is not coprime with \( x \).

For example, when \( N = 12156144 \):

Valid lists include: \( (42), (616, 6, 91, 23), (91, 616, 6, 23), (66, 7), (66, 7, 7, 23, 299, 66), \\ (143, 13, 66), (42, 12156144), \text{etc.} \)

Invalid lists include: \( (5, 11) \) because 5 is not a divisor of \( N \); and \( (66, 13, 143) \) because 143 is not coprime with the other two numbers.

Now, Elly wants you to calculate the number of distinct valid lists that can be generated for a given \( N \).

Two lists are considered different if they have different lengths or if there exists a position where the values in the two lists differ.

Input Format

A single integer: \( N \).

Output Format

An integer representing the number of lists modulo \( (10^9 + 7) \).

Sample Input and Output

Sample Input #1

6

Sample Output #1

28

Sample Input #2

203021

Sample Output #2

33628

Sample Input #3

60357056536

Sample Output #3

907882

Sample Input #4

12156144

Sample Output #4

104757552

Notes

Sample Explanation

Sample 1 Explanation

Valid lists include: \( (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) \)

There are a total of 28 such lists.

Sample 4 Explanation

The actual answer is \( 14104757650 \).

Output \( 14104757650 \bmod (10^9 + 7) = 104757552 \)

Data Constraints

• For all data, \( 1 \le N \le 10^{15} \)
• For about 30% of the data, \( N \) has at most 2 prime factors.
• For about 60% of the data, \( N \) has at most 4 prime factors.
• For 100% of the data, \( N \) has at most 6 prime factors.

Source

Original problem from: eJOI 2017 Problem B Six

Translation provided by: @_Wallace_

见题面 Input 部分

见题面 Output 部分