Busy Beaver sème à nouveau le chaos au marché fermier ! Cette fois, il déclenche une bataille de nourriture parmi les stands.

Les stands sont numérotés de $1$ à $N$ et sont reliés par $N - 1$ routes, formant un arbre. En d'autres termes, il est possible de voyager de n'importe quel stand à n'importe quel autre en suivant les routes, et il existe exactement un chemin simple entre deux stands quelconques.

Busy Beaver assigne chaque stand soit à l'équipe Patate, soit à l'équipe Tomate comme suit :

• Il commence au stand 1, parcourt les routes, visite chaque stand, et revient finalement au stand 1. Parmi tous ces itinéraires, il en choisit un avec le nombre total minimal de routes parcourues.
• Le stand 1 est assigné à l'équipe Patate.
• Chaque fois que Busy Beaver visite un stand pour la première fois (autre que le stand 1), il l'assigne immédiatement à l'une des deux équipes. Pour que le combat soit équitable, il alterne l'assignation d'équipe à chaque fois qu'il assigne un nouveau stand. C'est-à-dire que si le stand le plus récemment assigné a été attribué à l'équipe Patate, alors le prochain stand nouvellement visité doit être assigné à l'équipe Tomate, et vice versa.

Votre tâche est de compter le nombre d'assignations d'équipe possibles. Notez que différents itinéraires de longueur minimale peuvent produire la même assignation finale ; de telles assignations ne doivent être comptées qu'une seule fois. Comme la réponse peut être énorme, donnez-la modulo $10^9 + 7$.

Entrée

La première ligne contient un entier unique $T$ ($1 \le T \le 10^4$) — le nombre de cas de test.

La première ligne de chaque cas de test contient un entier unique $N$ ($2 \le N \le 10^5$).

Chacune des $N - 1$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le N, u \neq v$), indiquant qu'il y a une route entre les stands $u$ et $v$.

La somme de $N$ sur tous les cas de test n'excède pas $2 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un entier unique : le nombre d'assignations d'équipe finales possibles modulo $10^9 + 7$.

Scoring

Il y a trois sous-tâches pour ce problème :

• (10 points) : Les stands forment un graphe en étoile enraciné au stand 1. Plus précisément, le stand 1 a $N - 1$ routes connectées à lui.
• (20 points) : Les stands forment un arbre binaire enraciné au stand 1. Plus précisément, le stand 1 a au plus 2 routes connectées à lui, et chaque autre stand a au plus 3 routes connectées à lui.
• (70 points) : Aucune contrainte supplémentaire.

Exemples

Entrée 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

Sortie 1

2
20
8
12

Remarque

Le cas de test 1 satisfait la deuxième sous-tâche (arbre binaire).

Le cas de test 2 satisfait la première sous-tâche (graphe en étoile).

Le cas de test 3 satisfait la deuxième sous-tâche (arbre binaire).

Le cas de test 4 satisfait la troisième sous-tâche (aucune contrainte supplémentaire).

Dans le premier cas de test, une assignation d'équipe possible est illustrée ci-dessous.

Un itinéraire de longueur minimale est : $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$.

Sa longueur totale est de 6, ce qui est le minimum possible pour un itinéraire qui commence au stand 1, visite chaque stand et revient au stand 1.

Les stands sont ensuite assignés dans l'ordre dans lequel ils sont visités pour la première fois :

• Le stand 1 est assigné à l'équipe Patate.
• Le stand 2 est assigné à l'équipe Tomate.
• Le stand 3 est assigné à l'équipe Patate.
• Le stand 4 est assigné à l'équipe Tomate.

L'autre assignation d'équipe possible est obtenue en visitant le stand 4 avant le stand 3, ce qui échange leurs équipes. Par conséquent, le nombre total d'assignations d'équipe possibles est 2.