First, start by reading the problem statement for Carmichael Numbers.

For this prelude, you are to compute the power of one number to a second number modulo a third number.

Input consists of a sequence of lines, with each line containing three integers, a, n, and p (each less than 65000), separated by spaces. The last line contains three 0s, which should not be processed.

For each dataset, compute a ^ n mod p, printing the result in the format shown below.

3 2 2
5 3 7
4 13 497
0 0 0

3 ^ 2 mod 2 is 1.
5 ^ 3 mod 7 is 6.
4 ^ 13 mod 497 is 445.