Great Pow!

Write the power $a^b$ as $\mathrm{pow}_a(b)$.

Then define $\mathrm{pow}_a^0(a) = a$ and $\mathrm{pow}_a^{k+1}(a) = \mathrm{pow}_a\bigl(\mathrm{pow}_a^k(a)\bigr)$ for $k \ge 0$.

Given $a$ and $k$, compute $\mathrm{pow}_a^k(a)$, the value of the tower built from $k+1$ copies of $a$:

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

The tower is evaluated from the top down. For $k = 2$, note that $(a^a)^a \neq a^{(a^a)}$, and the value you need is the latter.

The first line contains $a$ and $k$ separated by a space. ($1 \le a \le 10^9$, $0 \le k \le 10^9$)

Print $\mathrm{pow}_a^k(a)$ modulo $a+1$. The value itself can be enormous, so only the remainder is printed.

$\mathrm{pow}_2^3(2) = 2^{2^{2^{2}}} = 65536$, so print 65536 modulo 3, which is 1.