Un árbol binario perfecto es un árbol con raíz donde cada nodo no 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 se convierte en un árbol binario perfecto al enraizarlo en uno de sus nodos.

Bessie tiene un árbol con ~N~ nodos. Determina el número de maneras de eliminar un subconjunto de aristas del árbol de forma que el bosque resultante sea una colección de árboles binarios perfectos sin raíz. Dado que la respuesta puede ser muy grande, muestra el resultado módulo ~10^9 + 7~.

Entrada

La primera línea contiene un entero ~T~, 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~ 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~ en todos los casos de prueba no supera ~2 \cdot 10^5~.

Salida

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

Restricciones

• ~1 \leq N \leq 10^5~
• ~1 \leq T \leq 100~
• ~1 \leq u_i, v_i \leq N~

Puntuación

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

Elemplo de Entrada

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

Ejemplo de Salida

8
2
14

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 genera dos subárboles de altura 1, el último seis de altura 0, y los demás tres subárboles de altura 0 y uno de altura 1.