A^B mod C

Given a, b, c find the value of a^(b) mod c (1 ≤ a, b, c < 2^63).

Input

Contains multiple test cases. Each test is given in one line and contains three integers a, b and c.

Output

For each test case print on a separate line the value of a^(b) mod c.

Examples