Дана перестановка $[1, 2, \ldots, n]$ длины $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 (10 баллов): $n \le 10$.

Подзадача #2 (10 баллов): $n \le 18$.

Подзадача #3 (10 баллов): $n \le 50$.

Подзадача #4 (30 баллов): $n \le 300$.

Подзадача #5 (40 баллов): без дополнительных ограничений.

Примеры

Пример 1

Входные данные

3 998244353

Выходные данные

1
5
6

Примечание 1

Для $n=3$ при выполнении не более $1$ операции можно получить все перестановки, кроме $[3, 2, 1]$.

Пример 2

Входные данные

1 100000007

Выходные данные

1

Пример 3

Входные данные

20 1000000009

Выходные данные

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

Примечание 3

Обратите внимание, что ответ должен быть выведен по модулю $m$.