Description

Calculate R = (B^P) mod M for large B, P, and M. Integer B is in the range 0 to 2³² inclusive. Integer P is in the range 0 to 2³¹ inclusive. Integer M is in the range 1 to 65600 inclusive. Note that you cannot calculate R directly because B^P 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.

Case 1: 0 <= B <= 2¹⁵, 0 <= P <= 2¹⁵, 1 <= M <= 46340
Case 2: 0 <= B <= 2¹⁵, 0 <= P <= 2³¹, 1 <= M <= 46340
Case 3: 0 <= B <= 2³¹, 0 <= P <= 2³¹, 1 <= M <= 46340
Case 4: 0 <= B <= 2³², 0 <= P <= 2³¹, 1 <= M <= 65600

Output

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

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss