Районная олимпиада по информатике 2009 года за 9 класс | Казахстанские олимпиады

Задача F. Степень

Вам даны целые числа $A$, $B$ и $C$. Выведите остаток от деления $A^B$ ($A$ в степени $B$) на $C$. Обратите внимание: $(X · Y) mod Z = ((X mod Z) · (Y mod Z)) mod Z$

Формат входного файла

Единственная строка входного файла содержит 3 целых числа: $A$, $B$, $C$ ($0 <= A, B <= 10^{18}$, $1 <= C <= 10^{18}$). Числа разделены пробелами.

Формат выходного файла

Выходной файл должен содержать одно число – ответ к задаче.

Примеры

Вход

3 4 5

Выход

1