配点 : 100 点
問題文
正整数 N 和素数 由 M 。 对于
(, ?, ) 组成的字符串,满足以下条件。 好字符串 。
- 包含在字符串中
?分别 定义(或 通过替换为)通过将其替换为 平衡括号序列 。
长度 小于或等于 2N 中的好字符串数为 M 后求余数。
但是, 运算前设定中包含的平衡括号序列 是满足以下任一条件的字符串。
- 空文字列
- 平衡的括号序列 A 存在,
由
(, A,)按此顺序连接而成的字符串 - 一组非空平衡括号 A,B 存在, 由A,B 按此顺序连接而成的字符串
制約
- 1\leq N\leq 9\times 10^{8}
- 9\times 10^{8}\leq M\leq 10^{9}
- M 是质数 答案可以由
- 所有输入均为整数
部分点
- 附加限制 如果正确答案是满足 N\leq 5\times 10^{6} 的数据集 给出 70 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N M
出力
打印答案。 来自
入力例 1
1 998244353
出力例 1
4
长度是 2N=2 的一个好的字符串是
案例 (), (?, ?), ?? 可以得到第 4 一。
请注意,无法创建
入力例 2
2 900000011
出力例 2
28
入力例 3
999937 999999937
出力例 3
170733195
入力例 4
167167924 924924167
出力例 4
596516682
入力例 4 不包含在部分分数中。