题目描述

给定一棵 $ n $ 个点的树，节点编号为 $ 1 $ 到 $ n $ ；每次从剩余的边中等概率随机选择一条边删除并合并它连接的两个节点（合并方法是，等概率（即 $ 1/2 $ ）选择其中一个节点，将剩余的与它相连边的这一端连到另一个节点上，最后删除选择的节点），直到树上只剩下唯一的一个节点；现在你需要计算每个节点成为最终剩余的这个节点的概率；概率对 $ 10^9+7 $ 取模。

输入格式

第一行一个正整数 $ n $ 代表树上的节点数，紧接着 $ n-1 $ 行每行两个正整数 $ a_i $ 和 $ b_i $ 表示一条连接 $ a_i $ 与 $ b_i $ 的边。保证输入是一棵树， $ 1 \leq n \leq 500, 1 \leq a_i,b_i \leq n $ 。

输出格式

一行 $ n $ 个非负整数分别表示每个节点成为最终剩余节点的概率取模后的结果，每两个数间以一个空格分隔。

样例 1

input

4
1 2
1 3
1 4

output

125000001 291666669 291666669 291666669

只有每次选择边时 $ 1 $ 号节点都以 $ 1/2 $ 概率剩下 $ 1 $ 号才能剩余到最后，所以概率是 $ 1/8 $ ，而其它三个节点等价，概率为 $ 7/24 $ 。

样例 2

input

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

output

467773441 982421882 485351566 128906251 485351566 982421882 467773441

树退化为了一条链。

样例 3

input

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

output

937239590 849609381 937239590 937239590 112890626 112890626 112890626

数据范围与提示

改编自 CF1060F 没想到loj评测机这么快。。。时限调整为标程2倍了。。。