N - Bracket Sequestion
Editorial
/


Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 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 のケースは部分点には含まれません。