Description

Input

The first line contains two integers $n$ and $p$ ($2 \le n \le 2000$, $10^8 + 7 \le p \le 10^9+9$). It's guaranteed that $p$ is a prime number.

Each of the next $n-1$ lines contains two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$), representing an edge between $u_i$ and $v_i$.

It is guaranteed that the given edges form a tree.

Output

The only line contains $n-1$ integers — the answer modulo $p$ for $k=1,2,\ldots,n-1$.

4 998244353
1 2
2 3
1 4

1 6 6

7 100000007
1 2
1 3
2 4
2 5
3 6
3 7

1 47 340 854 880 320

8 1000000007
1 2
2 3
3 4
4 5
5 6
6 7
7 8

1 126 1806 8400 16800 15120 5040

Note

In the first test case, when $k=1$, the only possible way is:

1. $\{1,2,3,4\} \to \{1\}$.

When $k=2$, there are $6$ possible ways:

1. $\{1,2,3,4\} \to \{1,2\} \to \{1\}$;
2. $\{1,2,3,4\} \to \{1,2,3\} \to \{1\}$;
3. $\{1,2,3,4\} \to \{1,2,4\} \to \{1\}$;
4. $\{1,2,3,4\} \to \{1,3\} \to \{1\}$;
5. $\{1,2,3,4\} \to \{1,3,4\} \to \{1\}$;
6. $\{1,2,3,4\} \to \{1,4\} \to \{1\}$.

When $k=3$, there are $6$ possible ways:

1. $\{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\}$;
2. $\{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\}$;
3. $\{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\}$;
4. $\{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\}$;
5. $\{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\}$;
6. $\{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\}$.