Exponial

There are many ways to build very large numbers. Two of them are:

• Exponentiation: $42^{2016} = \underbrace{42 \times 42 \times \cdots \times 42}_{2016 \text{ times}}$
• Factorials: $2016! = 2016 \times 2015 \times \cdots \times 2 \times 1$

This problem uses their lesser known combination, the exponial, which is defined for every positive integer $n$ as

$\mathrm{exponial}(n) = n^{(n-1)^{(n-2)^{\cdots^{2^1}}}}$

For example, $\mathrm{exponial}(1) = 1$ and $\mathrm{exponial}(5) = 5^{4^{3^{2^1}}} \approx 6.206 \times 10^{183230}$, which is already very large. Exponentiation is right associative, so $a^{b^c} = a^{(b^c)}$.

Exponials are too large to handle directly. Write a program that computes the remainder of $\mathrm{exponial}(n)$ divided by $m$.

The first line contains two integers $n$ and $m$ separated by a space ($1 \le n \le 10^9$, $1 \le m \le 10^9$).

Print the remainder of $\mathrm{exponial}(n)$ divided by $m$ on one line.