P5153 A Simple Function

This problem is an adaptation; special thanks to classmate Wu Zuofan.

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

A single line containing a positive integer $n$.

A single line with the required result.

- 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