User Tools

Site Tools


prelude_two_to_carmichael_numbers_--_efficient_power_mod

Prelude to Carmichael Numbers -- Efficient Power Mod

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

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.

Output

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

Sample Input

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

Sample Output

3 ^ 2 mod 2 is 1.
5 ^ 3 mod 7 is 6.
4 ^ 13 mod 497 is 445.
prelude_two_to_carmichael_numbers_--_efficient_power_mod.txt · Last modified: 2011/09/25 06:54 by jtkorb