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