Nanachi and Euler Totient
/

## Algebra, Euler's totient function, Mathematics, Number Theory

Problem
Editorial
Analytics

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$

SAMPLE INPUT
12
SAMPLE OUTPUT
32
Explanation

The divisors of $12$ are $1, 2, 3, 4, 6$ and $12$ i.e $f(n) = \phi(1)\cdot\phi(2)\cdot\phi(3)\cdot\phi(4)\cdot\phi(6)\cdot \phi(12)$

$\Rightarrow f(n) = 1\cdot 1\cdot 2\cdot 2\cdot 2\cdot 4 = 32$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...