J. Степень за логарифм

Вычислите $a^b \bmod m$.

Умножать $b$ раз нельзя: показатель до $10^{18}$. Рекурсия справляется за логарифм:

Обратите внимание, что при чётном $b$ вызов один, а не два: если написать $a^{b/2} \cdot a^{b/2}$ двумя вызовами, глубина останется логарифмической, а число вызовов станет линейным по $b$.

Одна строка содержит числа $a$, $b$ и $m$ ($0 \le a \le 10^{18}$, $0 \le b \le 10^{18}$, $1 \le m \le 10^{18}$).

Одно число — $a^b \bmod m$.