Busy Beaver はプログラミングを諦め、現代アートに挑戦することにしました！

Busy Beaver は塗料のついた 2 つのトークンを持っています。彼は無向グラフを次のように塗りつぶしたいと考えています。

• 最初はすべての頂点が未塗装です。まず、Busy Beaver は一方のトークンを頂点 1 に、もう一方を頂点 2 に置きます。
• 次に、彼はグラフの辺に沿ってトークンをスライドさせます。トークンが頂点の上を通るたびに、その頂点は塗装されます。（頂点 1 と 2 は最初から塗装されていることに注意してください。）
• プロセス中のどの時点においても、2 つのトークンが辺で直接つながることなく、すべての頂点を塗装することが可能である場合、そのグラフは「芸術的」であると呼ばれます。

$N$ 個の頂点を持つ芸術的な無向グラフの数を求めてください。答えは非常に大きくなる可能性があるため、素数 $P$ で割った余りを出力してください。

入力

各テストケースの唯一の行には、2 つの整数 $N$ と $P$ が含まれます ($2 \le N \le 5000$; $5 \cdot 10^8 < P < 10^9$)。$P$ は素数です。

出力

$N$ 個の頂点を持つ芸術的な無向グラフの数を $P$ を法として出力してください。

入出力例

入力 1

2 799999999

出力 1

1

入力 2

3 998244853

出力 2

2

入力 3

1984 998244853

出力 3

424428556

注記

最初のテストケースでは、2 つの頂点と辺を持たないグラフが唯一の芸術的なグラフです。

2 番目のテストケースでは、以下の図の最初の 2 つのグラフが芸術的です。最後のグラフは、頂点 3 を塗装することが不可能であるため、芸術的ではありません。