Modular Exponentiation

Time limit

0.5s

Memory limit

128 MB

Problem

Given natural numbers A, B, and C, compute the remainder when A^B is divided by C. The value of A^B can be very large, so compute the remainder efficiently.

Input

The first line contains A, B, and C separated by spaces. Each of A, B, and C is a natural number not greater than 2,147,483,647.

Output

Print the remainder when A^B is divided by C.