AT_ttpc2023_n Bracket Sequestion

给定正整数 $N$ 和素数 $M$。 我们定义如下条件的字符串为**好字符串**： 字符串仅由 `(`、`?`、`)` 组成，并且可以将其中的每个 `?` 替换为 `(` 或 `)`，使得整个字符串变为一个**平衡括号序列**。 长度为 $2N$ 的好字符串的个数对 $M$ 取余的结果是多少？ **平衡括号序列**满足下列条件之一： - 空字符串； - 存在某个平衡括号序列 $A$，使得将 `(`、$A$、`)` 按顺序连接得到该字符串； - 存在某些非空的平衡括号序列 $A,B$，使得将 $A,B$ 按顺序连接得到该字符串。

输入从标准输入读取，格式如下： > $N$ $M$

输出答案。

## 部分分 - 满足额外限制 $N\leq 5\times 10^{6}$ 的数据点可以获得 $70$ 分。 ## 样例解释 1 长度为 $2N=2$ 的好字符串有 `()`、`(?`、`?)`、`??` 共 $4$ 个。 ## 样例解释 4 输入样例 4 中的情况未包含在部分分的范围内。 ## 数据范围 - $1\leq N\leq 9\times 10^{8}$ - $9\times 10^{8}\leq M\leq 10^{9}$ - $M$ 是素数 - 输入均为整数。 由 ChatGPT 5 翻译