Problem F
Exponial

Illustration of $\mathrm{exponial}(3)$ (not to scale), Picture by C.M. de Talleyrand-Périgord via Wikimedia Commons

• Exponentiation: ${42}^{2016}=\underset{2016\text{ times}}{\underbrace{42\cdot 42\cdot \dots \cdot 42}}$.

• Factorials: $2016!=2016\cdot 2015\cdot \dots \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

For example, $\mathrm{exponial}(1)=1$ and $\mathrm{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 $\mathrm{exponial}(n)modm$ (the remainder of $\mathrm{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 $\mathrm{exponial}(n)modm$.

2 42

2

5 123456789

16317634

94 265

39