给定一个正整数 $N$ 和一个质数 $M$。

如果一个由 (, ?, ) 组成的字符串满足以下条件，则称其为“好的”：

• 通过将字符串中的每个 ? 替换为 ( 或 )，可以将其转换为一个合法的括号序列。

请找出长度为 $2N$ 的“好的”字符串的数量，结果对 $M$ 取模。

在此，合法括号序列定义如下：

• 空字符串。
• 若 $A$ 是一个合法括号序列，则将 (、$A$、) 按此顺序连接得到的字符串也是合法括号序列。
• 若 $A$ 和 $B$ 是非空合法括号序列，则将 $A$、$B$ 按此顺序连接得到的字符串也是合法括号序列。

输入格式

输入通过标准输入给出，格式如下：

$N \ M$

• 输入中的所有值均为整数。
• $1 \le N \le 9 \times 10^8$
• $9 \times 10^8 \le M \le 10^9$
• $M$ 是一个质数。

输出格式

输出答案。

样例

输入格式 1

1 998244353

输出格式 1

4

说明

在第一个样例中，长度为 $2N(= 2)$ 的“好的”字符串共有 4 个：()，(?，?)，??。

输入格式 2

2 900000011

输出格式 2

28

输入格式 3

999937 999999937

输出格式 3

170733195

输入格式 4

167167924 924924167

输出格式 4

596516682