Description

Calculate R = (B^P) mod M for large B, P, and M. Integer B and P are in the range 0 to 2147483647 (=2³¹ – 1) inclusive. Integer M is in the range 1 to 46340 inclusive. Note you cannot calculate R directly because M is too large.

Input

There are multiple test cases. Each test case is given in three lines, containing B, P, and M in each line.

Output

For each test case, output the answer R in a single line.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss