Un árbol binario perfecto es un árbol con raíz donde cada nodo que no es hoja tiene exactamente dos hijos y todos los nodos hoja están a la misma distancia de la raíz.

Un árbol binario perfecto sin raíz es un árbol sin raíz que es un árbol binario perfecto cuando se le asigna una raíz en uno de sus nodos.

Bessie tiene un árbol con $N$ ($1 \le N \le 10^5$) nodos. Determine el número de formas de eliminar un subconjunto de aristas del árbol de modo que el bosque resultante sea una colección de árboles binarios perfectos sin raíz. Como la respuesta puede ser muy grande, imprima el resultado módulo $10^9+7$.

Entrada

La primera línea contiene un entero $T$ ($1 \leq T \leq 100$), el número de casos de prueba independientes.

La primera línea de cada caso de prueba contiene un entero $N$.

Cada una de las siguientes $N-1$ líneas de cada caso de prueba contiene dos enteros $u_i$ y $v_i$ ($1 \leq u_i, v_i \leq N$) que indican una arista entre los nodos $u_i$ y $v_i$.

Se garantiza que, para cada caso de prueba, las aristas dadas forman un árbol con $N$ nodos.

Además, la suma de $N$ sobre todos los casos de prueba no supera $2\cdot 10^5$.

Salida

Para cada caso de prueba, imprima un único entero: el número de subconjuntos de aristas que, al eliminarse, resultan en un bosque que es una colección de árboles binarios perfectos sin raíz, módulo $10^9+7$.

Ejemplos

Entrada 1

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

Salida 1

8
2
14

Nota

En el primer caso de prueba, Bessie puede eliminar cualquiera de los siguientes subconjuntos de aristas para obtener un bosque de árboles binarios perfectos:

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)$

El primer subconjunto resulta en dos subárboles de altura $1$, el último subconjunto resulta en seis subárboles de altura $0$, y los otros subconjuntos resultan en tres subárboles de altura $0$ y un subárbol de altura $1$.

Subtareas

• Entradas 2-3: $N\le 15$
• Entradas 4-5: Ningún nodo es adyacente a más de dos otros nodos.
• Entradas 6-9: $N\le 1000$, la suma de $N$ no supera $2000$, y ningún nodo es adyacente a más de tres otros nodos.
• Entradas 10-13: Ningún nodo es adyacente a más de tres otros nodos.
• Entradas 14-21: Sin restricciones adicionales.