暂无测试数据。

蒜头君在书上翻到了一个递推式：

$$\displaystyle f_1 = f_2 = 1$$

$$\displaystyle f_n = (f_{n - 1} \times f_{n - 1} + f_{n - 2}) \mod p$$

现在，蒜头君告诉你 $n$ 和 $p$，你能帮他算出 $f_n$ 吗？

输入格式

输入一行，包含两个整数 $n, p$

输出格式

输出一行，表示答案

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 20, 1 \leq p \leq 10 ^ 4$

对于 $60\%$ 的数据，$1 \leq n \leq 10^5, 1 \leq p \leq 10^4$

对于 $100\%$ 的数据，$1 \leq n \leq 10^5, 1 \leq p \leq 10^9$。

5 5

2