AT_agc075_e [AGC075E] Many Optimization Problems

> **Optimization Problem**長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。また、長さ $ N+1 $ の非負整数列 $ X=(0,0,\dots,0) $ があります。 > > あなたは今から $ i=1,2,\dots,N $ について以下の操作を行います。 > > - $ 0 \le v \le A_i $ を満たす整数 $ v $ を選び、 $ X_i,X_{i+1} $ にそれぞれ $ v,A_i-v $ を加算する。 > > 操作終了時の $ X $ の最大値としてあり得る値の最小値を求めてください。 正整数 $ N,M $ と素数 $ P $ が与えられます。長さ $ N $ かつ総和が $ M $ であるような非負整数列 $ A=(A_1,A_2,\dots,A_N) $ 全てに対する **Optimization Problem** の答えの総和を $ P $ で割った余りを求めてください。

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

**Optimization Problem** の答えの総和を $ P $ で割った余りを出力せよ。

### Sample Explanation 1 例えば、 $ A=(1,0,2) $ について **Optimization Problem** を解きます。例えば、操作列の一例として以下のようなものがあります。 - $ i = 1 $ では $ v = 1 $ とする。 $ X=(1,0,0,0) $ となる。 - $ i = 2 $ では $ v = 0 $ とする。 $ X=(1,0,0,0) $ となる。 - $ i = 3 $ では $ v = 1 $ とする。 $ X=(1,0,1,1) $ となる。 $ X $ の最大値を $ 0 $ 以下にすることは出来ないため、答えは $ 1 $ です。 これ以外に答えが $ 1 $ となる数列が $ 6 $ 個、答えが $ 2 $ となる数列が $ 3 $ 個あるためその総和は $ 13 $ です。 ### Constraints - $ 1 \le N \le 100 $ - $ 1 \le M \le 10^{18} $ - $ 9 \times 10^8 \le P \le 10^9 $ - $ P $ は素数