Problems
A^B mod C
A^B mod C
Given a, b, c find the value of a^(b)
mod c (1 ≤ a, b, c < 2^63
).
Input data
Contains multiple test cases. Each test is given in one line and contains three integers a, b and c.
Output data
For each test case print on a separate line the value of a^(b)
mod c.
Examples
Input example #1
3 2 4 2 10 1000
Output example #1
1 24