Given a permutation $[1, 2, \ldots, n]$ of length $n$, you can perform the following operation:

• Choose a number, remove it, and place it at either the beginning or the end of the permutation.

For each $k=0, 1, \ldots, n-1$, find the number of permutations that can be obtained by performing at most $k$ operations. Since these numbers can be very large, you only need to output their values modulo $m$.

Input

A single line containing two integers $n$ and $m$ ($1\le n\le 1000$, $10^8\le m\le 10^9+9$, $m$ is a prime number).

Output

$n$ lines, where the $i$-th line contains an integer representing the answer for $k=i-1$.

Examples

Input 1

3 998244353

Output 1

1
5
6

Note 1

For $n=3$, all permutations except $[3, 2, 1]$ can be obtained by performing at most $1$ operation.

Input 2

1 100000007

Output 2

1

Input 3

20 1000000009

Output 3

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

Note 3

Note that the answers must be taken modulo $m$.

Subtasks

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): No additional constraints.