树生成的数组

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一棵包含 $n$ 个结点的树，结点编号为 $1,2,\ldots,n$。按以下随机过程依次标记结点：

1. 初始没有结点被标记，从整棵树中等概率选择一个结点并标记；
2. 此后，从所有尚未标记且至少与一个已标记结点相邻的结点中，等概率选择一个并标记；
3. 重复上一步，直到所有结点都被标记。

按结点被标记的先后顺序记录其编号，得到数组 $a$。求数组 $a$ 的逆序对数量的期望。

若期望写成最简分数 $p/q$，输出 $p\cdot q^{-1}\bmod(10^9+7)$。可以证明分母在模 $10^9+7$ 意义下可逆。

输入格式

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $x,y$，表示树中有一条连接结点 $x$ 与 $y$ 的边。

输出格式

输出一个整数，表示期望逆序对数量对 $10^9+7$ 取模的结果。

样例输入 1

3
1 2
1 3

样例输出 1

166666669

数据范围

$2\le n\le200$；输入保证给出的边构成一棵树。