There are many different traffic plans, and little Ivica is interested in only one question: how interesting will his trip to school be!
We can imagine that Zagreb consists of $N$ districts labeled with numbers from $1$ to $N$. Between some pairs of districts $i$ and $j$ (where $i < j$) there are one-way streets. A traffic plan consists of some set of such one-way streets.
Ivica's house is located in district $1$, and the school is in district $N$. He is now interested, for each $K$ from $0$ to $N$, in how many traffic plans exist such that the number of districts that lie on some possible path from district $1$ to district $N$ is exactly $K$.
Since these numbers can be very large, he is interested in their remainder when divided by $P$.
Input
The first line contains the natural numbers $N$ and $P$.
Output
In a single line, print $N + 1$ numbers, where the $i$-th number represents the number of traffic plans with $i - 1$ significant districts modulo $P$.
Constraints
In all subtasks, $2 \le N \le 2000$ and $10^8 \le P \le 10^9 + 100$, where $P$ is a prime number.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 4 | $N \le 7$ |
| 2 | 7 | $N \le 18$ |
| 3 | 23 | $N \le 50$ |
| 4 | 13 | $N \le 100$ |
| 5 | 18 | $N \le 300$ |
| 6 | 35 | No additional constraints |
Examples
Input 1
2 1000000007
Output 1
1 0 1
Input 2
3 1000000007
Output 2
3 0 3 2
Input 3
5 1000000007
Output 3
183 0 183 286 250 122
Note
Explanation of the second example:
$K = 0$ holds for the traffic plans: $\{\}$ $\{(1, 2)\}$ * $\{(2, 3)\}$
$K = 2$ holds for the traffic plans: $\{(1, 3)\}$ $\{(1, 3), (1, 2)\}$ * $\{(1, 3), (2, 3)\}$
$K = 3$ holds for the traffic plans: $\{(1, 2), (2, 3)\}$ $\{(1, 2), (1, 3), (2, 3)\}$