You are asked to compute A^B (A to the power of B) (1 <= A,B <= 100 000 000). You surely understand that this number can be quite astonishing and i don't like big numbers unless they are on my paycheck so I'm just interested in the reminder of A^B mod C (1<= C <= 1000000)

Input

Three integers A B and C.

Output

Single integer - the result of the computation.

Example

Input:
2 10 1000

Output:
24