Description

Elly is studying some properties of a positive integer $N$, and she finds that $N$ has no more than $6$ distinct prime factors.

Next, she generates a list in a special way. The list is empty at the beginning. Each time, she writes down a divisor $x$ of $N$ that is greater than $1$ and adds it to the list. Before adding $x$, she must ensure that among all numbers already in the list, there are 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 both of the other numbers.

Now Elly wants you to compute, for a given $N$, how many different valid lists can be generated.

We say two lists are different if their lengths are different, or if there exists a position where the values at that position are different.

Input Format

One integer: $N$.

Output Format

One integer, the number of lists modulo $(10^9+7)$.

6

28

203021

33628

60357056536

907882

12156144

104757552

Hint

【Explanation of Samples】

Sample 1 Explanation

The lists that satisfy the condition 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)$.

There are $28$ lists in total.

Sample 4 Explanation

The real answer is $14104757650$.

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

【Constraints and Notes】

• For all testdata, it is guaranteed that $1\le N\le 10^{15}$.
• For about $30\%$ of the testdata, $N$ has at most $2$ prime factors.
• For about $60\%$ of the testdata, $N$ has at most $4$ prime factors.
• For $100\%$ of the testdata, $N$ has at most $6$ prime factors.

【Notes】

The original problem is from: eJOI 2017 Problem B Six.

Translation provided by: @_Wallace_.

Translated by ChatGPT 5