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^18). Numbers are separated by spaces. Output Output file must contain only one non-negative integer less than C - the answer to the problem.

Examples