Modular Exponentiation

Input

The input contains three positive integers $x$, $n$, $m$ \left(1 \leq x, m \leq 10^9,\ 2 \leq n \leq 10^7\right).

Output

Print one integer — the value of x^n \bmod m.

Examples