Alice 和 Bob 准备玩著名的“石头剪刀布”游戏。他们都不喜欢多动脑筋，因此两人都将采用随机策略：以相等的概率选择石头、剪刀或布。

他们想要进行 $n$ 局游戏，然后按照以下方式计算得分 $s$：如果 Alice 赢了 $a$ 次，Bob 赢了 $b$ 次，剩下的 $n - a - b$ 局为平局，则得分为 $a$ 和 $b$ 的最大公约数。如果 $a$ 或 $b$ 为 $0$，我们定义 $a$ 和 $b$ 的最大公约数为 $a + b$。

计算 $s \cdot 3^{2n}$ 的期望值。注意，该答案必然是一个整数。由于这个整数可能非常大，请输出其对 $p$ 取模后的结果。

输入格式

输入包含两个整数 $n$ 和 $p$ ($1 \le n \le 10^5$, $10^8 \le p \le 10^9$, $p$ 为质数)。

输出格式

输出一行，包含一个整数：问题的答案对 $p$ 取模的结果。

样例

样例输入 1

1 998244353

样例输出 1

6

样例输入 2

2 998244353

样例输出 2

90