Marbles Per Second

R0k0_N RUET CodeSmash 2020
Limits 1s, 512 MB

You have a rooted tree of nn nodes. If we traverse the tree from the root, let’s say the traversing order is a >ba \space -> b. Then aa is the parent and bb is the child. The leaf nodes have no child. The root is always node 11.

The following process happens each second:
1. The root produces a marble.
2. If a node contains a marble and it has at least one child, it is transferred to one of its children with uniform probability.
3. If the node is a leaf node. It stores the marble.

A node can store infinite numbers of marbles. What is the expected number of marbles the root has to produce so that every leaf has at least one marble stored in it.

Input

Each test contains multiple test cases. The first line contains the number of test cases t(1t2000)t(1\leq t\leq 2000). Description of the test cases follows.

The first line of each test case contains a single integer n (1n200000)n (1\leq n\leq 200000)  — the number of vertices in the tree.

Each of the next n−1 lines contains two integers xx and yy (1x,yn)(1\leq x,y\leq n), meaning there is an edge between vertices xx and yy in the tree.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of n over all test cases does not exceed 200000200000.

Output

For each test case, output a single line containing a single integer denoting the answer for that test case modulo 109+710^9+7.

Sample

InputOutput
1
6
1 2
2 3
3 4
4 5
5 6
1

Submit

Login to submit.

Statistics

100% Solution Ratio
OnikJahanSagorEarliest, 4M ago
OnikJahanSagorFastest, 0.0s
OnikJahanSagorLightest, 16 MB
SpellMasterShortest, 587B
Toph uses cookies. By continuing you agree to our Cookie Policy.