問題文

コンテストで使う $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$ で割った余りを求めてください。

制約

• $2 \\leq N \\leq 5000$
• $9 \\times 10^8 < M < 10^9$
• $M$ は素数である。
• 入力中のすべての値は整数である。

入力

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

$N$ $M$

出力

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

入力例 1

2 998244353

出力例 1

3

可能な配点の付け方は $(1, 1)$, $(1, 2)$, $(2, 2)$ です。

入力例 2

3 998244353

出力例 2

7

可能な配点の付け方は $(1, 1, 1)$, $(1, 2, 2)$, $(1, 3, 3)$, $(2, 2, 2)$, $(2, 2, 3)$, $(2, 3, 3)$, $(3, 3, 3)$ です。

入力例 3

6 966666661

出力例 3

66

入力例 4

96 925309799

出力例 4

83779