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

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

Ограничение по времени Ограничение по памяти
2 seconds 64 megabytes

Вам даны целые числа AA, BB и CC. Выведите остаток от деления ABA^B (AA в степени BB) на CC. Обратите внимание: (XY)modZ=((XmodZ)(YmodZ))modZ(X · Y) mod Z = ((X mod Z) · (Y mod Z)) mod Z

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

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

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

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

Примеры

Вход

3 4 5

Выход

1