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 翻译