A15188. Partial Virtual Trees

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](https://en.wikipedia.org/wiki/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$ .

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\}$ .