Busy Beaver está causando caos en el mercado de agricultores de nuevo. Esta vez, está iniciando una guerra de comida entre los puestos.

Los puestos están numerados del $1$ al $N$ y están conectados por $N - 1$ caminos, formando un árbol. En otras palabras, es posible viajar desde cualquier puesto a cualquier otro puesto siguiendo los caminos, y existe exactamente un camino simple entre dos puestos cualesquiera.

Busy Beaver asigna cada puesto al Equipo Patata o al Equipo Tomate de la siguiente manera:

• Comienza en el puesto $1$, viaja a lo largo de los caminos, visita cada puesto y finalmente regresa al puesto $1$. Entre todas esas rutas, elige una con el número total mínimo posible de caminos recorridos.
• El puesto $1$ se asigna al Equipo Patata.
• Cada vez que Busy Beaver visita un puesto por primera vez (que no sea el puesto $1$), lo asigna inmediatamente a uno de los dos equipos. Para mantener la pelea justa, alterna la asignación de equipo cada vez que asigna un nuevo puesto. Es decir, si el puesto asignado más recientemente fue asignado al Equipo Patata, entonces el siguiente puesto recién visitado debe ser asignado al Equipo Tomate, y viceversa.

Tu tarea es contar el número de posibles asignaciones de equipo. Ten en cuenta que diferentes rutas de longitud mínima pueden producir la misma asignación final; dichas asignaciones deben contarse solo una vez. Dado que la respuesta puede ser enorme, imprímela módulo $10^9 + 7$.

Entrada

La primera línea contiene un solo entero $T$ ($1 \le T \le 10^4$) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene un solo entero $N$ ($2 \le N \le 10^5$).

Cada una de las siguientes $N - 1$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le N, u \neq v$), indicando que hay un camino entre los puestos $u$ y $v$.

La suma de $N$ en todos los casos de prueba no supera $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un solo entero: el número de posibles asignaciones finales de equipo módulo $10^9 + 7$.

Puntuación

Existen dos subtareas para este problema:

• (10 puntos): Los puestos forman un grafo estrella con raíz en el puesto $1$. Más específicamente, el puesto $1$ tiene $N - 1$ caminos conectados a él.
• (20 puntos): Los puestos forman un árbol binario con raíz en el puesto $1$. Más específicamente, el puesto $1$ tiene a lo sumo $2$ caminos conectados a él, y cada otro puesto tiene a lo sumo $3$ caminos conectados a él.
• (70 puntos): Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

2
20
8
12

Nota

La muestra contiene 4 casos de prueba:

• El caso de prueba 1 satisface la segunda subtarea (árbol binario).
• El caso de prueba 2 satisface la primera subtarea (grafo estrella).
• El caso de prueba 3 satisface la segunda subtarea (árbol binario).
• El caso de prueba 4 satisface la tercera subtarea (sin restricciones adicionales).

En el primer caso de prueba, una posible asignación de equipo se muestra a continuación.

Una ruta de longitud mínima es: 1 → 2 → 3 → 2 → 4 → 2 → 1.

Su longitud total es 6, que es la más pequeña posible para una ruta que comienza en el puesto 1, visita cada puesto y regresa al puesto 1.

Los puestos se asignan entonces en el orden en el que son visitados por primera vez:

• El puesto 1 se asigna al Equipo Patata.
• El puesto 2 se asigna al Equipo Tomate.
• El puesto 3 se asigna al Equipo Patata.
• El puesto 4 se asigna al Equipo Tomate.

La otra posible asignación de equipo se obtiene visitando el puesto 4 antes que el puesto 3, lo cual intercambia sus equipos. Por lo tanto, el número total de posibles asignaciones de equipo es 2.