威尔与颠倒怪物有心灵联系,所以怪物知道的一切,威尔都知道。突然,他开始画画,一页又一页,不停歇。乔伊斯、他的妈妈和霍珀酋长把这些图画放在一起,他们意识到,这是一棵贴有标签的树!
树是连通的非循环图。威尔的树有 n 个顶点。乔伊斯和霍珀不知道这意味着什么,所以他们正在调查这棵树和类似的树。对于每个 k,使得 0 ≤ k ≤ n - 1,他们将调查所有具有 n 个顶点且与 Will 的树共享 k 个边的所有标记树。当且仅当存在一对顶点 (v, u),使得一棵树中 v 和 u 之间存在边,而另一棵树中不存在边时,两棵标记树是不同的。
Hopper 和 Joyce 想知道他们需要做多少工作,因此他们要求您告诉他们,对于每个 k,有 n 个顶点且与 Will 的树完全共享 k 个边的标记树的数量。答案可能非常大,所以他们只要求你告诉他们答案模 1000000007 = 109 + 7。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 100) — 树的大小。
接下来的 n - 1 行包含 Will 树的边缘。每行包含两个整数 v 和 u (1 ≤ v, u ≤ n, v ≠ u),即边的端点。保证给定的图是一棵树。
输出
在一行中打印 n 个整数。第 i 个整数应该是具有 n 个顶点且与 Will 的树完全共享 i - 1 条边的标记树的数量,模 1000 000 007 = 109 + 7。
示例
输入 #1
3 1 2 1 3
输出 #1
0 2 1
输入 #2
4 1 2 2 3 3 4
输出 #2
1 7 7 1
输入 #3
4 1 2 1 3 1 4
输出 #3
0 9 6 1