Problem E
modexp

Implement modular exponentiation from modular multiplication, e.g., using the square-and-multiply algorithm. You are obviously not allowed to use any built-in modular exponentiation function, e.g., pow in Python, but you are allowed to use built-in multiplication and division algorithms.

Input

Each line of the input consists of a space-separated list of: an integer basis $a$, an integer exponent $e$, and an integer modulus $n$. All integers are positive and given in decimal.

Output

For each input line, output a line containing the unique integer $r\in \{ 0,\ldots ,n-1\} $ such that $a^ e=r\bmod n$. The output integers should be given in decimal.

3 3 5
0 1 5
1 5 7

2
0
1