Description

Define a multiplicative function $f(x)$, and $f(p ^ k) = p ^ k(p ^ k - 1)$ ($p$ is a prime). Compute

modulo $10 ^ 9 + 7$.

Input Format

One line containing an integer $n$.

Output Format

Output one integer, the answer.

10

263

1000000000

710164413

Hint

$f(1)=1$，$f(2)=2$，$f(3)=6$，$f(4)=12$，$f(5)=20$；
$f(6)=12$，$f(7)=42$，$f(8)=56$，$f(9)=72$，$f(10)=40$。

For $30\%$ of the testdata, it is guaranteed that $1\le n\le 10^6$.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^{10}$。

Translated by ChatGPT 5