Remarque : La limite de mémoire pour ce problème est de 512 Mo, soit le double de la limite par défaut.

Un arbre binaire parfait est un arbre enraciné où chaque nœud non-feuille possède exactement deux enfants et où toutes les feuilles sont à une distance égale de la racine.

Un arbre binaire parfait non enraciné est un arbre non enraciné qui devient un arbre binaire parfait lorsqu'il est enraciné en l'un de ses nœuds.

Bessie possède un arbre avec $N$ ($1 \le N \le 10^5$) nœuds. Déterminez le nombre de façons de supprimer un sous-ensemble d'arêtes de l'arbre de sorte que la forêt résultante soit une collection d'arbres binaires parfaits non enracinés. Comme la réponse peut être très grande, donnez le résultat modulo $10^9+7$.

Entrée

La première ligne contient un entier $T$ ($1 \leq T \leq 100$), le nombre de cas de test indépendants.

La première ligne de chaque cas de test contient un entier $N$.

Chacune des $N-1$ lignes suivantes de chaque cas de test contient deux entiers $u_i$ et $v_i$ ($1 \leq u_i, v_i \leq N$) indiquant une arête entre les nœuds $u_i$ et $v_i$.

Il est garanti que pour chaque cas de test, les arêtes données forment un arbre avec $N$ nœuds.

De plus, la somme des $N$ sur tous les cas de test ne dépasse pas $2\cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un seul entier : le nombre de sous-ensembles d'arêtes qui, une fois supprimés, résultent en une forêt composée d'arbres binaires parfaits non enracinés, modulo $10^9+7$.

Exemples

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

Sortie 1

8
2
14

Remarque

Dans le premier cas de test, Bessie peut supprimer l'un des sous-ensembles d'arêtes suivants pour obtenir une forêt d'arbres binaires parfaits :

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

Le premier sous-ensemble résulte en deux sous-arbres de hauteur $1$, le dernier sous-ensemble résulte en six sous-arbres de hauteur $0$, et les autres sous-ensembles résultent en trois sous-arbres de hauteur $0$ et un sous-arbre de hauteur $1$.

Sous-tâches

• Entrées 2-3 : $N\le 15$
• Entrées 4-5 : Aucun nœud n'est adjacent à plus de deux autres nœuds.
• Entrées 6-9 : $N\le 1000$, la somme des $N$ ne dépasse pas $2000$, et aucun nœud n'est adjacent à plus de trois autres nœuds.
• Entrées 10-13 : Aucun nœud n'est adjacent à plus de trois autres nœuds.
• Entrées 14-21 : Aucune contrainte supplémentaire.

Crédits du problème : Avnith Vijayram