Note: The memory limit for this problem is 512MB, twice the default.

A perfect binary tree is a rooted tree where every non-leaf node has exactly two children and all leaf nodes are at an equal distance from the root.

An unrooted perfect binary tree is an unrooted tree that is a perfect binary tree when rooted at one of its nodes.

Bessie has a tree with $N$ ($1 \le N \le 10^5$) nodes. Determine the number of ways to remove a subset of edges from the tree so that the resulting forest is a collection of unrooted perfect binary trees. As the answer may be very large, output the result modulo $10^9+7$.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains an integer $T$ ($1 \leq T \leq 100$), the number of independent test cases.

The first line of each test case contains an integer $N$.

Each of the next $N-1$ lines of each test case contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$) indicating an edge between nodes $u_i$ and $v_i$ .

It is guaranteed that for each test case, the given edges form a tree with $N$ nodes.

Additionally, the sum of $N$ over all test cases does not exceed $2\cdot 10^5$.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a single integer: the number of subsets of edges that, when removed, result in a forest that is a collection of unrooted perfect binary trees, modulo $10^9+7$.

SAMPLE INPUT:

3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 5

SAMPLE OUTPUT:

8
2
14

In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees:

1. $(2, 6)$
2. $(1, 2)$, $(2, 3)$, $(2, 6)$
3. $(1, 2)$, $(2, 3)$, $(4, 6)$
4. $(1, 2)$, $(2, 3)$, $(5, 6)$
5. $(1, 2)$, $(4, 6)$, $(5, 6)$
6. $(2, 6)$, $(4, 6)$, $(5, 6)$
7. $(2, 3)$, $(4, 6)$, $(5, 6)$
8. $(1, 2)$, $(2, 3)$, $(2, 6)$, $(4, 6)$, $(5, 6)$

The first subset results in two subtrees of height $1$, the last subset results in six subtrees of height $0$, and the other subsets result in three subtrees of height $0$ and one subtree of height $1$.

SCORING:

• Inputs 2-3: $N\le 15$
• Inputs 4-5: No node is adjacent to more than two other nodes.
• Inputs 6-9: $N\le 1000$, the sum of $N$ does not exceed $2000$, and no node is adjacent to more than three other nodes.
• Inputs 10-13: No node is adjacent to more than three other nodes.
• Inputs 14-21: No additional constraints.

Problem credits: Avnith Vijayram