Description

你有一棵无根树（n个结点，1~n标号），和一个整数k。

对于一个树上的结点集合S，可以用一个子树把S中的点全部包含，这里子树指的是原树结点的一个子集，并且这些结点全部连通。对于集合S，令f(S)表示这样的子树最少所包含的结点数目。

共有C(n,k)种方法选出树上的k个结点。对于其中每种方法，设选出的点集为S，你需要求出所有这样的f(S)的总和。

答案可能很大，需要对10^9+7（一个质数）取模。

你需要对所有k=1~n都回答上述问题。

Format

Input

第一行整数n。

接下来n-1行每行表示一条边的两个结点。保证输入是一棵树。

Output

输出n行，第i行表示k=i时的答案，模10^9+7。

Samples

3
1 2
2 3

3
7
3

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

7
67
150
179
122
45
7

Hint

对于10%的数据n<=10。

对于20%的数据n<=200。

对于40%的数据n<=2000。

对于另外20%的数据，树上第i个结点均匀随机地与

{1,2,...,i-1}中某个点连边。

对于100%的数据，n<=200000。