Big Mod

Calculate R = B^P mod M for large values of B, P, and M, using an efficient algorithm. (That's right, this problem has a strict time limit!)

Input Specification

The input contains several test cases. Each test case consists of three integer values, in the order B, P, M, one number per line. B and P are integers in the range 0 to 2 147 483 647, inclusive. M is an integer in the range 1 to 46 340, inclusive. Consecutive test cases are separated by a blank line. The input is terminated by end-of-file (EOF).

Output Specification

For each test case, print one line containing a single integer, the result of the computation.

Sample Input

1. 3
2. 18132
3. 17
5. 17
6. 1765
7. 3
9. 2374859
10. 3029382
11. 36123

download as text file

Output for Sample Input

1. 13
2. 2
3. 13195

download as text file