Living alone with Mitty in the Abyss, Nanachi has developed an interest in number theory problems. Nanachi recently came up with the following problem but is unable to solve it.

Let $\phi(n)$ denote the count of positive integers up to n which are coprime with n. Since summations bore our Nanachi, Nanachi decided to evaluate the function $f(n)$ instead which is defined as:

$\displaystyle f(n) = \prod_{d|n} \phi(d)$

where $a|b$ mean a divides b. Nanachi seeks your help in finding the value of $f(n)$.

INPUT
A single integer n

OUTPUT
Value of $f(n)$. Since this value can be large, output it modulo $10^9 + 7$.

CONSTRAINTS
$1 \leq n \leq 10^{12}$

For 10% of the testcases, $n \leq 10^6$