Степень по модулю

Вычислите остаток от деления $a^b$ на $m$.

Показатель может быть огромным, поэтому возводить в степень напрямую нельзя.

Три числа в одной строке: $a$ от $0$ до $10^9$, $b$ от $0$ до $10^{18}$ и $m$ от $1$ до $10^9$.

Одно число.

Чётную степень можно свести к половинной: $a^{2k}$ — это квадрат $a^k$. Так глубина рекурсии оказывается около шестидесяти вместо миллиарда.