Dla danej permutacji $[1, 2, \ldots, n]$ możesz wykonać następującą operację:

• Wybierz liczbę, wyjmij ją i umieść na początku lub na końcu permutacji.

Dla każdego $k = 0, 1, \ldots, n-1$ wyznacz liczbę permutacji, które można uzyskać, wykonując co najwyżej $k$ operacji. Ponieważ liczby te mogą być bardzo duże, należy podać wynik modulo $m$.

Wejście

W jednym wierszu znajdują się dwie liczby całkowite $n, m$ ($1 \le n \le 1000$, $10^8 \le m \le 10^9+9$, $m$ jest liczbą pierwszą).

Wyjście

$n$ wierszy, gdzie $i$-ty wiersz zawiera liczbę całkowitą będącą odpowiedzią dla $k = i-1$.

Przykład

Przykład 1

Wejście

3 998244353

Wyjście

1
5
6

Uwagi 1

Dla $n=3$, wykonując co najwyżej $1$ operację, można uzyskać wszystkie permutacje poza $[3, 2, 1]$.

Przykład 2

Wejście

1 100000007

Wyjście

1

Przykład 3

Wejście

20 1000000009

Wyjście

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

Uwagi 3

Pamiętaj, że wynik należy podać modulo $m$.

Podzadania

Podzadanie #1 (10 punktów): $n \le 10$.

Podzadanie #2 (10 punktów): $n \le 18$.

Podzadanie #3 (10 punktów): $n \le 50$.

Podzadanie #4 (30 punktów): $n \le 300$.

Podzadanie #5 (40 punktów): Brak dodatkowych ograniczeń.