The 2016 Nordic Collegiate Programming Contest

Start

2016-10-08 11:00 CEST

The 2016 Nordic Collegiate Programming Contest

End

2016-10-08 16:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -411 days 5:55:10

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Exponial

/problems/exponial/file/statement/en/img-0001.jpg
Illustration of $\operatorname {exponial}(3)$ (not to scale), Picture by C.M. de Talleyrand-PĂ©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:
  • Exponentiation: $42^{2016} = \underbrace{42 \cdot 42 \cdot \ldots \cdot 42}_{2016\text { times}}$.

  • Factorials: $2016! = 2016 \cdot 2015 \cdot \ldots \cdot 2 \cdot 1$.

In this problem we look at their lesser-known love-child the exponial, which is an operation defined for all positive integers $n$ as

\[ \operatorname {exponial}(n) = n^{(n-1)^{(n-2)^{\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 right-associative: $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