Illustration of
$\operatorname {exponial}(3)$ (not
to scale),
Picture by C.M. de TalleyrandPĂ©rigord via Wikimedia
Commons
Everybody loves big numbers (if you do not, you might
want to stop reading at this point). There are many ways of
constructing really big numbers known to humankind, for
instance:
In this problem we look at their lesserknown lovechild the
exponial, which is an operation defined for all
positive integers $n$
as
\[ \operatorname
{exponial}(n) = n^{(n1)^{(n2)^{\cdots ^{2^{1}}}}}. \]
For example, $\operatorname
{exponial}(1) = 1$ and $\operatorname {exponial}(5) =
5^{4^{3^{2^1}}} \approx 6.206 \cdot 10^{183230}$ which
is already pretty big. Note that exponentiation is
rightassociative: $a^{b^ c} =
a^{(b^ c)}$.
Since the exponials are really big, they can be a bit
unwieldy to work with. Therefore we would like you to write a
program which computes $\operatorname {exponial}(n) \bmod m$
(the remainder of $\operatorname
{exponial}(n)$ when dividing by $m$).
Input
The input consists of two integers $n$ ($1
\le n \le 10^9$) and $m$ ($1
\le m \le 10^9$).
Output
Output a single integer, the value of $\operatorname {exponial}(n) \bmod
m$.
Sample Input 1 
Sample Output 1 
2 42

2

Sample Input 2 
Sample Output 2 
5 123456789

16317634

Sample Input 3 
Sample Output 3 
94 265

39
