На космической станции есть лазер с усилителем. Каждую секунду мощность лазера умножается на коэффициент усиления A. Начальная мощность лазера = 1 единица. Нужно узнать мощность через N секунд.
Но есть проблема: мощность может стать АСТРОНОМИЧЕСКИ большой! Поэтому бортовой компьютер показывает результат по модулю M.
Определите, что покажет бортовой компьютер после N секунд.
ВХОДНЫЕ ДАННЫЕ:
Три числа A, N, M (1 ≤ A, M ≤ 10^9, 0 ≤ N ≤ 10^18)
ВЫХОДНЫЕ ДАННЫЕ:
Одно число - ответ на задачу
Примеры
| № | Входные данные | Выходные данные |
|
1
|
123456789 1 1000000000
|
123456789
|