Play on Tree

Problem Description

Trees are very interesting, so playing on them is also very interesting.One day, Satono Diamond and Kitasan Black were playing a game on a tree. First, Satono Diamond selected a point as the root of the tree. Then Kitasan Black began the game. Each round selected a node $x$ and deleted it and its subtree. Whoever deleted the root node lost. Kitasan Black wanted to know if she could win, but she didn't know which root node it was, so she assumed that the root node was randomly selected by Satono Diamond.Please tell her the probability of winning. Please output it modulo $10^9+7$.

Input

The input consists of multiple test cases. The first line contains a single integer $T(1 \leq T \leq 3)$ — the number of test cases. The first line of each test case contains one integer $n$ $(1 \leq n \leq 2\times 10^5)$ — the number of nodes in the tree. Each of the next ${n-1}$ lines contains three integers $u,v$ $(1 \leq u,v \leq n,u \neq v)$

Output

For each query, output an integer in a single line indicating the probability of winning

Sample Input

2
2
1 2
3
1 2
1 3

Sample Output

1
666666672

Source

2023“钉耙编程”中国大学生算法设计超级联赛（1）