По трем натуральным числам x, n и m вычислить значение xn mod m.

Входные данные

Три натуральных числа x, n, m (1 ≤ x, m ≤ 109, 2 ≤ n ≤ 107).

Выходные данные

Вывести xn mod m.