For given A, B and M to compute A^B mod M.

Input

In the input file are three natural numbers A, B and M (1 ≤ A, B ≤ 1018, 2 ≤ M ≤ 2*109), записанные в одной строке через пробел.

Output

In the output file write a number equal to A^B mod M.