D-几只毛毛虫？_【小羊肖恩】小羊杯 Round 2

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一天，在生物课上，老师带着小羊和他的同学去公园观察动物。

他看到了草丛里有很多毛毛虫，于是他想，毛毛虫有什么特征呢？
于是他把一条毛毛虫抽象成了一棵有 $n$ 个节点的树。树是一个有 $n$ 个点 $n-1$ 条无向边组成的连通图。

这棵树被称为一条毛毛虫，当且仅当：树上存在一条路径 $u_1\to u_2\to\dots\to u_k\ (k\geq2)$ ，使得 $u_i,u_{i+1}\ (1\leq i \lt k)$ 有边，且 $u_1,u_2,\dots,u_k$ 两两不同；同时对于树上任一点 $v$ ，路径上存在一点到 $v$ 的距离不超过 $1$ 。

因为在 “是毛毛虫吗？” 中小羊画了太多毛毛虫，现在小羊觉得画毛毛虫太无聊了，于是他随便画了 $T$ 棵树，并一棵一棵地问你：用橡皮擦擦掉一些边和点的话，能形成多少只不同的毛毛虫呢？

只要两条毛毛虫包含了不同的节点，我们就认为这两条毛毛虫是不同的。
因为不同的毛毛虫的数量可能很多，请将答案关于 $10^9+7$ 取模后输出。
注意：我们认为单点 不形成 毛毛虫，因为找不到满足定义的路径。两条毛毛虫不同，当且仅当至少存在一个点在其中一条毛毛虫中，而不在另一条毛毛虫中。

输入描述:

第一行输入一个整数  ，表示小羊画的树有  棵。
接下来输入  棵树。
对于每一棵树，第一行输入整数  ，表示这棵树的顶点的个数，这棵树的顶点为  。
接下来的  行，每行输入两个整数  ，表示顶点  之间连接了无向边。
保证输入的每一个图都是一棵树，且所有样例对应  的和不超过  。

输出描述:

对于每一棵树，输出一行，在该行输出一个整数，表示该树通过擦去边和点，可以得到的不同的毛毛虫的数量，并将结果关于  取模。

示例1

输入

复制

输出

复制

7
6

说明

对于第一棵树，以下顶点集和原图中集内点之间存在的边构成毛毛虫：  。
对于第二棵树，以下顶点集和原图中集内点之间存在的边构成毛毛虫：  。
故答案分别为  。