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