For given A, B and M to compute A^B mod M.
In the input file are three natural numbers A, B and M (1 ≤ A, B ≤ 10^18, 2 ≤ M ≤ 2*10^9), записанные в одной строке через пробел.
1 ≤ A
B ≤ 10^18
2 ≤ M ≤ 2
10^9
In the output file write a number equal to A^B mod M.