

Big ModCalculate 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 SpecificationThe 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 endoffile (EOF). Output SpecificationFor each test case, print one line containing a single integer, the result of the computation. Sample Input
Output for Sample Input


University of Debrecen; Faculty of Informatics; v. 05/24/2018 