409652: GYM103660 E Disjoint Path On Tree

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Disjoint Path On Treetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a tree consisting of $$$n$$$ vertices. Recall that a tree is an undirected connected acyclic graph.

Now, calculate the number of simple path pairs that each pair of simple paths does not pass through the same vertex. Note that $$$pair(Path_i,Path_j)$$$ and $$$pair(Path_j,Path_i)$$$ should only be calculated once. As the answer may be too big, output the answer module $$$10^9+7$$$.

The simple path is the path that visits each vertex at most once. The path only visits a single vertex is also a path.

Input

The first line contains a single integer $$$T (1 \le T \le 2 \times 10^5)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n (1 \le n \le 2 \times 10^5)$$$ — the number of vertices.

The next $$$n-1$$$ lines of each test case describe the edges of the tree in form of $$$u_i, v_i(1\le u_i,v_i \le n, u_i \ne v_i)$$$. It is guaranteed that given graph is a tree.

It is guaranteed that $$$\sum{n} \le 2 \times 10^5$$$ over all test cases.

Output

For each test case, output a single integer in a line — the answer module $$$10^9+7$$$.

ExampleInput
1
3
1 2
1 3
Output
5
Note

$$$5$$$ pairs of paths in the sample are:

  • $$$(1,2)$$$
  • $$$(1,3)$$$
  • $$$(2,3)$$$
  • $$$(1-2,3)$$$
  • $$$(1-3,2)$$$

加入题单

上一题 下一题 算法标签: