Calculate R = BP mod M for large values of B, P, and M, using an efficient algorithm. (That's right, this problem has a strict time limit!)
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).
For each test case, print one line containing a single integer, the result of the computation.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 05/24/2018|