川城似鸟是一位热爱竞技节目的女孩。有一天,她发现了一棵由 $$$n$$$ 个顶点组成的有根树。根是顶点$$$1$$$。作为一个高级问题解决者,她很快就想到了一个问题。
Kawashiro Nitori 有一个顶点集 $$$U=\{1,2,\ldots,n\}$$$。她要和树和布景玩一个游戏。在每次操作中,她都会选择一个顶点集$$$T$$$,其中$$$T$$$是$$$U$$$的部分虚拟树,并将$$$U$$$更改为$$$T$$$。
顶点集 $$$S_1$$$ 是顶点集 $$$S_2$$$ 的部分虚拟树,如果 $$$S_1$$$ 是 $$$S_2$$$ 的子集,$$$S_1 \neq S_2$$$,并且对于 $$$i$$$ 和 $$$j$$$ 中的所有顶点对$$$S_1$$$, $$$\operatorname{LCA}(i,j)$$$ 位于 $$$S_1$$$ 中,其中 $$$\operatorname{LCA}(x,y)$$$ 表示树上顶点 $$$x$$$ 和 $$$y$$$ 的最低公共祖先。请注意,一个顶点集可以有许多不同的部分虚拟树。
Kawashiro Nitori想知道对于每一个可能的$$$k$$$,如果她精确地执行$$$k$$$次操作,她最终可以通过多少种方式得到$$$U=\{1\}$$$?如果存在整数 $$$z$$$ ($$$1 \le z \le k$$$) 使得在 $$$z$$$ 操作之后集合 $$$U$$$ 不同,则两种方式被认为是不同的。
由于答案可能非常大,因此您需要对 $$$p$$$ 求模。保证 $$$p$$$ 是素数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$2 \le n \le 2000$$$, $$$10^8 + 7 \le p \le 10^9+9$$$)。保证 $$$p$$$ 是素数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$、$$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示 $$$u_i$$$ 和 $$$v_i$$$ 之间的一条边。
保证给定的边形成一棵树。
输出
唯一一行包含 $$$n-1$$$ 整数 - 答案以 $$$p$$$ 为模,$$$k=1,2,\ldots,n-1$$$。
示例
输入 #1
4 998244353 1 2 2 3 1 4
输出 #1
1 6 6
输入 #2
7 100000007 1 2 1 3 2 4 2 5 3 6 3 7
输出 #2
1 47 340 854 880 320
输入 #3
8 1000000007 1 2 2 3 3 4 4 5 5 6 6 7 7 8
输出 #3
1 126 1806 8400 16800 15120 5040
注意
在第一个测试用例中,当 $$$k=1$$$ 时,唯一可能的方法是:
1. $$$\{1,2,3,4\} \到 \{1\}$$$。
当$$$k=2$$$时,有$$$6$$$可能的方式:
1. $$$\{1,2,3,4\} \到 \{1,2\} \到 \{1\}$$$;
2. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1\}$$$;
3. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1\}$$$;
4. $$$\{1,2,3,4\} \到 \{1,3\} \到 \{1\}$$$;
5. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1\}$$$;
6. $$$\{1,2,3,4\} \到 \{1,4\} \到 \{1\}$$$。
当$$$k=3$$$时,有$$$6$$$可能的方式:
1. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1,2\} \到 \{1\}$$$;
2. $$$\{1,2,3,4\} \到 \{1,2,3\} \到 \{1,3\} \到 \{1\}$$$;
3. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1,2\} \到 \{1\}$$$;
4. $$$\{1,2,3,4\} \到 \{1,2,4\} \到 \{1,4\} \到 \{1\}$$$;
5. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1,3\} \到 \{1\}$$$;
6. $$$\{1,2,3,4\} \到 \{1,3,4\} \到 \{1,4\} \到 \{1\}$$$。