给你一个无向无权树 $$$T$$$ ,有 $$$n$$$ 个顶点。
定义一个具有$$$n$$$顶点的完全无向带权图$$$G$$$,其中$$$G$$$中顶点$$$u$$$和$$$v$$$之间的边的权重等于原树中两个顶点之间的距离。
对于每个可能的顶点子集,考虑由该顶点子集导出的 $$$G$$$ 子图的最小生成树 (MST)。计算所有可能的顶点子集的 MST 权重之和。
由于这个数字很大,因此只需输出 $$$10^9 + 7$$$ 的模数即可。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10000$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$),即树中的顶点数。
下面的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$),表示树中顶点 $$$u$$$ 和 $$$v$$$ 之间的边。
保证所有测试用例的$$$n^2$$$总和不超过$$$5000^2$$$。
输出
输出一个整数,即所有可能的顶点子集的 MST 权重之和,以 $$$10^9+7$$$ 为模。
示例
输入复制
531 22 373 11 23 54 53 66 7224 119 73 1819 816 205 2213 2015 122 812 117 46 71 2110 187 320 1514 2118 48 1522 1711 14122 1
输出复制
64967406941601
注意
第一个测试用例如下所示。最多具有一个顶点的子集被忽略,因为它们的权重为 $$$0$$$,因此对总和没有贡献。