Partial Virtual Trees
Description
Kawashiro Nitori is a girl who loves competitive programming. One day she found a rooted tree consisting of $n$ vertices. The root is vertex $1$. As an advanced problem setter, she quickly thought of a problem.
Kawashiro Nitori has a vertex set $U=\{1,2,\ldots,n\}$. She's going to play a game with the tree and the set. In each operation, she will choose a vertex set $T$, where $T$ is a partial virtual tree of $U$, and change $U$ into $T$.
A vertex set $S_1$ is a partial virtual tree of a vertex set $S_2$, if $S_1$ is a subset of $S_2$, $S_1 \neq S_2$, and for all pairs of vertices $i$ and $j$ in $S_1$, $\operatorname{LCA}(i,j)$ is in $S_1$, where $\operatorname{LCA}(x,y)$ denotes the lowest common ancestor of vertices $x$ and $y$ on the tree. Note that a vertex set can have many different partial virtual trees.
Kawashiro Nitori wants to know for each possible $k$, if she performs the operation exactly $k$ times, in how many ways she can make $U=\{1\}$ in the end? Two ways are considered different if there exists an integer $z$ ($1 \le z \le k$) such that after $z$ operations the sets $U$ are different.
Since the answer could be very large, you need to find it modulo $p$. It's guaranteed that $p$ is a prime number.
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.
The only line contains $n-1$ integers — the answer modulo $p$ for $k=1,2,\ldots,n-1$.
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$.
Samples
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,2,3,4\} \to \{1\}$.
When $k=2$, there are $6$ possible ways:
- $\{1,2,3,4\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,4\} \to \{1\}$.
When $k=3$, there are $6$ possible ways:
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,3\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1,2\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,2,4\} \to \{1,4\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1,3\} \to \{1\}$;
- $\{1,2,3,4\} \to \{1,3,4\} \to \{1,4\} \to \{1\}$.