eolymp
bolt
Try our new interface for solving problems
Problems

Exponentiation - 2

Exponentiation - 2

Time limit 1 second
Memory limit 64 MiB

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