長さ $n$ の順列 $[1, 2, \ldots, n]$ に対して、以下の操作を行うことができます。

• 数を1つ選び、それを取り出して順列の先頭または末尾に移動させる。

各 $k=0, 1, \ldots, n-1$ について、最大 $k$ 回の操作によって得られる順列の個数を求めてください。これらの数は非常に大きくなる可能性があるため、$m$ で割った余りを出力してください。

入力

1行に2つの整数 $n, m$ が与えられます（$1\le n\le 1000$、$10^8\le m\le 10^9+9$、$m$ は素数）。

出力

$n$ 行出力してください。第 $i$ 行には $k=i-1$ のときの答えを出力してください。

入出力例

入力 1

3 998244353

出力 1

1
5
6

注記 1

$n=3$ のとき、最大 $1$ 回の操作で得られる順列は、$[3, 2, 1]$ を除くすべての順列です。

入力 2

1 100000007

出力 2

1

入力 3

20 1000000009

出力 3

1
39
1100
26220
554040
10581480
184187520
930255982
586386822
781249333
374807160
139825602
462558935
67876942
578348054
201415654
108018732
350356788
280522125
280522126

注記 3

答えは $m$ を法として計算する必要があることに注意してください。

小課題

Subtask #1 (10点): $n\le 10$。

Subtask #2 (10点): $n\le 18$。

Subtask #3 (10点): $n\le 50$。

Subtask #4 (30点): $n\le 300$。

Subtask #5 (40点): 追加の制約なし。