Битовая арифметика, модульная арифметика

Соревнование завершилось 29.09.18 в 23:00

A. В сухом остатке

Автор задачи: Соловьёв Виктор
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Паша только что научился быстро возводить числа в степень. Теперь ему нетерпится узнать, чему равна n-ная степень числа a. Числа a и n могут оказаться довольно большими, но Паше достаточно знать, чему равен остаток результата возведения a в степень n при делении на m.

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

Единственная строка входных данных содержит три целых числа: a, n и m (1 ≤ a, m ≤ 104, 0 ≤ n ≤ 109).

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

Вывести одно целое число - остаток от деления an на m.

Пример

Стандартный вводСтандартный вывод
2 10 10024
60 127 173152