Three positive integers x, n and m are given. Find the value of xn mod m.

Input

Three positive integers x, n, m (1 ≤ x, m ≤ 109, 2 ≤ n ≤ 107).

Output

Find and print the value of xn mod m.