给你一棵由 $$$n$$$ 节点组成的树。通过一一标记节点,可以从树中生成一个数组。
最初,当没有节点被标记时,从整棵树中等概率地选择并标记一个节点。
之后,直到所有节点都被标记,从一组未标记节点中等概率地选择并标记一个节点,该节点与标记节点至少有一条边。
可以看出,该过程标记了树中的所有节点。
最终数组 $$$a$$$ 是按每个节点被标记的时间顺序排列的节点标签列表。
查找由树和上述过程生成的数组中的预期反转次数。
数组 $$$a$$$ 中的反转数是满足 $$$i < j$$$ 且 $$$a_i > a_j$$$ 的索引对 $$$(i, j)$$$ 的数量。例如,数组 $$$[4, 1, 3, 2]$$$ 包含 $$$4$$$ 反转:$$$(1, 2)$$$、$$$(1, 3)$$$、$$$(1, 4)$$$、$$$(3, 4)$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200$$$) — 树中的节点数。
接下来的 $$$n - 1$$$ 行每行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \neq y$$$),表示节点 $$$x$$$ 和 $$$y$$$ 之间的边。
保证给定的边形成一棵树。
输出
输出生成的数组中预期的反转数,模 $$$10^9+7$$$。
正式地,令 $$$M = 10^9+7$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。
示例
输入 #1
3 1 2 1 3
输出 #1
166666669
输入 #2
6 2 1 2 3 6 1 1 4 2 5
输出 #2
500000009
输入 #3
5 1 2 1 3 1 4 2 5
输出 #3
500000007
注意
这是第一个样本中的树:
对于第一个示例,数组几乎是固定的。如果最初选择节点 $$$2$$$,则唯一可能的数组是 $$$[2, 1, 3]$$$ ($$$1$$$ 反转)。如果最初选择节点 $$$3$$$,则唯一可能的数组是 $$$[3, 1, 2]$$$ ($$$2$$$ 反转)。如果最初选择节点 $$$1$$$,则数组 $$$[1, 2, 3]$$$ ($$$0$$$ 反转)和 $$$[1, 3, 2]$$$ ($$$1$$$ 反转)是唯一的可能性和等概率。总共,预期的反转次数为 $$$\frac{1}{3}\cdot 1 + \frac{1}{3} \cdot 2 + \frac{1}{3} \cdot (\frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 1) = \frac{7}{6}$$$。
$$$166666669 \cdot 6 = 7 \pmod {10^9 + 7}$$$,所以答案是$$$166666669$$$。
这是第二个样本中的树:
这是第三个样本中的树: