A rolling checksum repeatedly raises a base to large powers under a modulus. Given three integers a, b, and m, compute (a ** b) mod m, the remainder when a raised to the power b is divided by m.

By convention a ** 0 = 1 for every a (including a = 0). The result must be the non-negative remainder in the range [0, m - 1]. Because b can be enormous, computing a ** b directly is infeasible — reduce modulo m as you go.

Input format

A single line with three space-separated integers a, b, and m.

Output format

A single integer: (a ** b) mod m.

Constraints

• 0 ≤ a ≤ 1000000000
• 0 ≤ b ≤ 1000000000000000
• 1 ≤ m ≤ 1000000000

Note: when m = 1 every remainder is 0.

2 10 1000

24

3 0 7

1