Tim Korb's Home Page

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

===== Prelude to Carmichael Numbers -- Efficient Power Mod ======

First, start by reading the problem statement for [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=35&page=show_problem&problem=947|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 =====

<code>
3 2 2
5 3 7
4 13 497
0 0 0
</code>

===== Sample Output =====

<code>
3 ^ 2 mod 2 is 1.
5 ^ 3 mod 7 is 6.
4 ^ 13 mod 497 is 445.
</code>