← 返回题目列表

AtCoder · ttpc2023_n

N. 括号序列问题

中文机器翻译题面 查看原题

配点 : 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 不包含在部分分数中。