AT_agc041_d [AGC041D] Problem Scores

[problemUrl]: https://atcoder.jp/contests/agc041/tasks/agc041_d コンテストで使う $ N $ 問の問題がジャッジに選ばれ、各問に配点を付ける段階になりました。 問題 $ i $ の配点 $ A_i $ は、$ 1 $ 以上 $ N $ 以下の整数でなければなりません。 また、すでに問題は難易度順に並んでおり、$ A_1\ \le\ A_2\ \le\ \ldots\ \le\ A_N $ でなければなりません (複数問の配点が同じになるのは構いませんが)。 ICPC のファンであるあなたは、解いた問題数が多い参加者ほど上位となってほしいと考えています。 この理由から、任意の $ k $ ($ 1\ \le\ k\ \le\ N-1 $) に対して、任意の $ k $ 問の配点の合計が任意の $ k+1 $ 問の配点の合計より真に小さくなるようにしたい、とあなたは考えています。 このような配点の付け方は何通りあるでしょうか？この数を与えられた素数 $ M $ で割った余りを求めてください。

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

配点の付け方の数を $ M $ で割った余りを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 5000 $ - $ 9\ \times\ 10^8\