每个人都喜欢大数（如果你不喜欢，现在可能想停止阅读了）。人类已知有许多构造极大数的方法，例如：

• 幂运算：$42^{2016} = \underbrace{42 \cdot 42 \cdot \dots \cdot 42}_{2016 \text{ 次}}$。
• 阶乘：$2016! = 2016 \cdot 2015 \cdot \dots \cdot 2 \cdot 1$。

exponial(3) 的示意图（非比例），图片由 C.M. de Talleyrand-Périgord 通过维基共享资源提供

在本题中，我们研究它们鲜为人知的“结晶”——“指数阶乘”（exponial），这是一种为所有正整数 $n$ 定义的运算：

$$\text{exponial}(n) = n^{(n-1)^{(n-2)^{\dots^{2^1}}}}$$

例如，$\text{exponial}(1) = 1$ 且 $\text{exponial}(5) = 5^{4^{3^{2^1}}} \approx 6.206 \cdot 10^{183230}$，这已经非常大了。注意幂运算是右结合的：$a^{b^c} = a^{(b^c)}$。

由于指数阶乘非常大，处理起来可能有些棘手。因此，我们希望你编写一个程序来计算 $\text{exponial}(n) \pmod m$（即 $\text{exponial}(n)$ 除以 $m$ 的余数）。

输入包含两个整数 $n$ ($1 \le n \le 10^9$) 和 $m$ ($1 \le m \le 10^9$)。

输出一个整数，即 $\text{exponial}(n) \pmod m$ 的值。

样例

输入格式 1

2 42

输出格式 1

2

输入格式 2

5 123456789

输出格式 2

16317634

输入格式 3

94 265

输出格式 3

39