题目描述

阿尼亚有读心术的超能力， 正因如此父亲黄昏以为他很聪明

今天， 父亲黄昏打算考验他的上限， 并给阿尼亚出了一个题

给定一个 $n$ 个节点的无根树， 每个点的编号 $index$ 唯一， 且 $index \in [1,n]$

父亲黄昏会先告诉你树的形态

父亲黄昏打算提问 $n$ 次， 第 $i$ 次询问他会问阿尼亚， 以 $i$ 为树根往下遍历的 $dfs$ 序的期望逆序对的数量对 $10^9+7$ 取模后答案是多少。

阿尼亚觉得自己做不到， 于是向你投来了呆滞的目光， 只要你会做， 她就会做， 当然， 如果你的回答时间超过了规定的时限， 那么阿尼亚会被黄昏鉴定为做不出来。

输入格式

一行一个整数 $n$

接下来 $n-1$ 行，每行两个整数 $u, v$ ，描述编号为 $u$ 的点和编号为$v$的点之间有一条连边

输出格式

$n$ 行， 每行一个整数， 用于描述第 $i$ 个询问的答案

样例

样例输入 #1

3
1 2
1 3

样例输出 #1

500000004
1
2

样例解释

$[1,3,2]$ 有 $1$ 个逆序对

$[1,2,3]$ 有 $0$ 个逆序对 则 $1$ 的答案是 $\frac{1}{2}$

$[2,1,3]$ 有 $1$ 个逆序对 则 $2$ 的答案是 $1$

$[3,1,2]$ 有 $2$ 个逆序对 则 $3$ 的答案是 $2$

数据范围

特殊点编号所代表的测试点特殊性质如下：

1. 对于所有 $i\ge 2$， 都有一条连向$1$的边， 形成一张以$1$为根的菊花图

2. 给出的数据为一条链。

对于所有数据，$1\leq n\leq 10^5$，对于所有对于对于所有 $1\leq i<n,\ 1\leq u_i,\ v_i\leq n,\ u_i\neq v_i$