Partial Virtual Trees

 Kawashiro Nitori is a girl who loves competitive programming. One day she found a rooted tree consisting of 

n$n$ vertices. The root is vertex 1$1$. As an advanced problem setter, she quickly thought of a problem.

Kawashiro Nitori has a vertex set U={1,2,…,n}$U=\{1,2,\dots ,n\}$. She's going to play a game with the tree and the set. In each operation, she will choose a vertex set T$T$, where T$T$ is a partial virtual tree of U$U$, and change U$U$ into T$T$.

A vertex set S1$S_1$ is a partial virtual tree of a vertex set S2$S_2$, if S1$S_1$ is a subset of S2$S_2$, S1≠S2$S_1\ne S_2$, and for all pairs of vertices i$i$ and j$j$ in S1$S_1$, LCA(i,j)$\mathrm{LCA}(i,j)$ is in S1$S_1$, where LCA(x,y)$\mathrm{LCA}(x,y)$ denotes the lowest common ancestor of vertices x$x$ and y$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$k$, if she performs the operation exactly k$k$ times, in how many ways she can make U={1}$U=\{1\}$ in the end? Two ways are considered different if there exists an integer z$z$ (1≤z≤k$1\le z\le k$) such that after z$z$ operations the sets U$U$ are different.

Since the answer could be very large, you need to find it modulo p$p$. It's guaranteed that p$p$ is a prime number.

Input

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

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

It is guaranteed that the given edges form a tree.

Output

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

Examples

input

Copy

4 998244353
1 2
2 3
1 4

output

Copy

1 6 6 

input

Copy

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

output

Copy

1 47 340 854 880 320 

input

Copy

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

output

Copy

1 126 1806 8400 16800 15120 5040 

Note

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

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

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

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

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

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