AT_ttpc2023_n Bracket Sequestion

正整数 $ N $ と素数 $ M $ が与えられます。 `(`, `?`, `)` からなる文字列で以下の条件を満たすものを **良い文字列** と定義します。 - 文字列に含まれる `?` をそれぞれ `(` あるいは `)` に置き換えることで **バランスの取れた括弧列** にすることができる。 長さ $ 2N $ の良い文字列の個数を $ M $ で割ったあまりを求めてください。 ただし、**バランスの取れた括弧列** とは以下のいずれかの条件を満たす文字列のことです。 - 空文字列 - あるバランスの取れた括弧列 $ A $ が存在して、`(`, $ A $ , `)` をこの順に連結した文字列 - ある空でないバランスの取れた括弧列 $ A,B $ が存在して、 $ A,B $ をこの順に連結した文字列

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

答えを出力せよ。

### 部分点 - 追加の制約 $ N\leq 5\times 10^{6} $ を満たすデータセットに正解した場合は $ 70 $ 点が与えられる。 ### Sample Explanation 1 長さが $ 2N=2 $ の良い文字列は `()`, `(?`, `?)`, `??` の $ 4 $ つです。 ### Sample Explanation 4 入力例 $ 4 $ のケースは部分点には含まれません。 ### Constraints - $ 1\leq N\leq 9\times 10^{8} $ - $ 9\times 10^{8}\leq M\leq 10^{9} $ - $ M $ は素数 - 入力は全て整数