Great Pow!

$a$의 거듭제곱 $a^b$를 $\mathrm{pow}_a(b)$로 쓰자.

그리고 $\mathrm{pow}_a^0(a) = a$, $\mathrm{pow}_a^{k+1}(a) = \mathrm{pow}_a\bigl(\mathrm{pow}_a^k(a)\bigr)$ ($k \ge 0$)로 정의한다.

$a$와 $k$가 주어질 때 $\mathrm{pow}_a^k(a)$를 구하라. 즉 $a$가 $k+1$개 쌓인 거듭제곱 탑

$a^{a^{a^{\cdots^{a}}}}$

의 값이다. 이 탑은 맨 위에서부터 계산한다. 예를 들어 $k = 2$이면 $(a^a)^a \neq a^{(a^a)}$이고, 구하는 값은 후자다.

첫째 줄에 $a$와 $k$가 공백으로 구분되어 주어진다. ($1 \le a \le 10^9$, $0 \le k \le 10^9$)

$\mathrm{pow}_a^k(a)$를 $a+1$로 나눈 나머지를 출력한다. 값 자체가 매우 커질 수 있어 나머지만 출력한다.

$\mathrm{pow}_2^3(2) = 2^{2^{2^{2}}} = 65536$이므로, 65536을 3으로 나눈 나머지인 1을 출력한다.