Given a, b, c find the value of a^(b) mod c (1 ≤ a, b, c < 2^63).
a^(b)
2^63
Contains multiple test cases. Each test is given in one line and contains three integers a, b and c.
For each test case print on a separate line the value of a^(b) mod c.