Modular Inverse

Hard#math #number-theory #fast-exponentiation· solved by 0 · time limit 2.0 s

Find $x$ with $a \cdot x \equiv 1 \pmod{10^9+7}$ , $0 \le x < 10^9+7$ .

Because $10^9+7$ is prime, Fermat's little theorem gives $x = a^{p-2} \bmod p$ .

Input

A single integer $a$ (not a multiple of $10^9+7$ ).

$x$

$1 \le a < 10^9+7$

Input

Output

500000004

Input

Output

333333336