問題文

正整数 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 点が与えられる。

入力例 1

1 998244353

出力例 1

4

長さが 2N=2 の良い文字列は (), (?, ?), ?? の 4 つです。

入力例 2

2 900000011

出力例 2

28

入力例 3

999937 999999937

出力例 3

170733195

入力例 4

167167924 924924167

出力例 4

596516682

入力例 4 のケースは部分点には含まれません。