빠른 거듭제곱

제한

• $1 \le a \le 1\,000\,000\,000$
• $0 \le n \le 1\,000\,000\,000$
• $a^n \le 10^{18}$

$n$을 1씩 줄이는 재귀는 $a = 1$, $n = 1\,000\,000\,000$에서 호출이 너무 깊어져 실행 중에 비정상 종료한다.

입출력 예시

입력 1

3 13

출력 1

1594323

입력 2

2 10

출력 2

1024