#P18495. Bracket Sequestion

Bracket Sequestion

Bracket Sequestion

给定正整数 NN 和质数 MM。仅由 (、?、) 组成的字符串,如果可以把其中每个 ? 替换成 ( 或 ),使整个字符串成为合法括号序列,就称为好字符串。

求长度为 2N2N 的好字符串数量,答案对 MM 取模。每个原字符串只计一次,即使它有多种合法替换方式。

合法括号序列定义如下:

  • 空字符串是合法括号序列;
  • 如果 AA 是合法括号序列,则依次拼接 (、AA、) 得到的字符串也是合法括号序列;
  • 如果 A,BA,B 均为非空合法括号序列,则拼接得到的 ABAB 也是合法括号序列。

输入格式

N M

所有输入值均为整数,且满足:

  • 1≤N≤9×1081\le N\le9\times10^8;
  • 9×108≤M≤1099\times10^8\le M\le10^9;
  • MM 是质数。

本题单组输入。

输出格式

输出答案对 MM 取模后的整数。

样例 1

1 998244353
4

长度为 2 的好字符串恰有 ()、(?、?)、?? 四个。

样例 2

2 900000011
28

样例 3

999937 999999937
170733195

样例 4

167167924 924924167
596516682