The Shortest does not Mean the S

Your are given integer numbers A, B and C. Output the remainder of division A^B (B-th power of A) by C.

Input
The only line of the input file contains three integers: A, B, C (1 <= A, B, C <= 10¹⁸). Numbers are separated by spaces.

Output
Output file must contain only one non-negative integer less than C - the answer to the problem.