You have a rooted tree of $n$ nodes. If we traverse the tree from the root, let’s say the traversing order is $a \space -> b$. Then $a$ is the parent and $b$ is the child. The leaf nodes have no child. The root is always node $1$.
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.
Each test contains multiple test cases. The first line contains the number of test cases $t(1\leq t\leq 2000)$. Description of the test cases follows.
The first line of each test case contains a single integer $n (1\leq n\leq 200000)$ — the number of vertices in the tree.
Each of the next n−1 lines contains two integers $x$ and $y$ $(1\leq x,y\leq n)$, meaning there is an edge between vertices $x$ and $y$ 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 $200000$.
For each test case, output a single line containing a single integer denoting the answer for that test case modulo $10^9+7$.
Input | Output |
---|---|
1 6 1 2 2 3 3 4 4 5 5 6 | 1 |