#P18495. Bracket Sequestion
Bracket Sequestion
Bracket Sequestion
给定正整数 和质数 。仅由 (、?、) 组成的字符串,如果可以把其中每个 ? 替换成 ( 或 ),使整个字符串成为合法括号序列,就称为好字符串。
求长度为 的好字符串数量,答案对 取模。每个原字符串只计一次,即使它有多种合法替换方式。
合法括号序列定义如下:
- 空字符串是合法括号序列;
- 如果 是合法括号序列,则依次拼接
(、、)得到的字符串也是合法括号序列; - 如果 均为非空合法括号序列,则拼接得到的 也是合法括号序列。
输入格式
N M
所有输入值均为整数,且满足:
- ;
- ;
- 是质数。
本题单组输入。
输出格式
输出答案对 取模后的整数。
样例 1
1 998244353
4
长度为 2 的好字符串恰有 ()、(?、?)、?? 四个。
样例 2
2 900000011
28
样例 3
999937 999999937
170733195
样例 4
167167924 924924167
596516682