老师在书上翻到了一个递推式：
$f_1 = f_2 = 1$
$f_n = (f_{n - 1} \times f_{n - 1} + f_{n - 2}) \mod p$
现在，告诉你 $n$ 和 $p$，你能帮他算出 $f_n$ 吗？

输入一行，包含两个整数 $n$，$p$。$1 \leq n \leq 10^5, 1 \leq p \leq 10^9$。

输出一行，表示答案。