Power with a remainder

Problem

Compute base to the power exp, modulo m, using recursion that halves the exponent. Read base, exp and m and print the result.

Example

Input

2
10
1000

Output

1024 % 1000.

Try the problem first. Open one hint at a time.

Hint 1

Compute the power for exp // 2 once and square it.

Hint 2

Multiply by base once more when exp is odd, and take % m after each multiplication.

Write your Python code, run it on the examples and submit it to hidden tests.