Description

HKE once discovered a very interesting function.

Define $f(2) = 1$. For $n \geq 3$, let $t$ be the smallest positive integer such that $n$ is not divisible by $t$, then $f(n) = f(t) + 1$.

For example, when $n = 6$, we have $t = 4$, and $f(6) = f(4) + 1 = f(3) + 2 = f(2) + 3 = 4$.

Now, HKE wants to know the value of $f(2) \times f(3) \times \cdots \times f(n)$. The answer can be large; please take it modulo $10^9 + 7$.

Input Format

A single line containing a positive integer $n$.

Output Format

A single line with the required result.

4

6

Hint

• For $30\%$ of the testdata, $n \leq 1000$.
• For $50\%$ of the testdata, $n \leq 1{,}000{,}000$.
• For $100\%$ of the testdata, $n \leq 10^{18}$.

Translated by ChatGPT 5