給定一個長度為 $n$ 的排列 $[1,2,\ldots,n]$，你可以進行以下操作：

• 選擇一個數，將其取出然後放到排列的開頭或末尾。

對每個 $k=0,1,\ldots,n-1$，求出進行至多 $k$ 次操作可能得到的排列個數。由於這些數可能非常大，你只需要回答它們除以 $m$ 的餘數即可。

輸入格式

一行兩個整數 $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 points): $n\le 10$。

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

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

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

Subtask #5 (40 points): 無額外限制。