Idealne drzewo binarne to drzewo ukorzenione, w którym każdy węzeł niebędący liściem ma dokładnie dwoje dzieci, a wszystkie liście znajdują się w tej samej odległości od korzenia.

Nieukorzenione idealne drzewo binarne to drzewo nieukorzenione, które staje się idealnym drzewem binarnym po wybraniu jednego z jego węzłów na korzeń.

Bessie posiada drzewo o $N$ ($1 \le N \le 10^5$) węzłach. Wyznacz liczbę sposobów usunięcia podzbioru krawędzi z drzewa tak, aby powstały las był zbiorem nieukorzenionych idealnych drzew binarnych. Ponieważ wynik może być bardzo duży, wyprowadź go modulo $10^9+7$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \leq T \leq 100$), liczbę niezależnych przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera liczbę całkowitą $N$.

Każda z kolejnych $N-1$ linii każdego przypadku testowego zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \leq u_i, v_i \leq N$), oznaczające krawędź między węzłami $u_i$ oraz $v_i$.

Gwarantuje się, że dla każdego przypadku testowego podane krawędzie tworzą drzewo o $N$ węzłach.

Dodatkowo, suma $N$ we wszystkich przypadkach testowych nie przekracza $2\cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wyprowadź jedną liczbę całkowitą: liczbę podzbiorów krawędzi, których usunięcie skutkuje lasem będącym zbiorem nieukorzenionych idealnych drzew binarnych, modulo $10^9+7$.

Przykład

Przykład 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

Wyjście 1

8
2
14

Uwagi

W pierwszym przypadku testowym Bessie może usunąć dowolny z następujących podzbiorów krawędzi, aby otrzymać las idealnych drzew binarnych:

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

Pierwszy podzbiór skutkuje dwoma poddrzewami o wysokości $1$, ostatni podzbiór skutkuje sześcioma poddrzewami o wysokości $0$, a pozostałe podzbiory skutkują trzema poddrzewami o wysokości $0$ i jednym poddrzewem o wysokości $1$.

Podzadania

• Testy 2-3: $N\le 15$
• Testy 4-5: Żaden węzeł nie jest połączony z więcej niż dwoma innymi węzłami.
• Testy 6-9: $N\le 1000$, suma $N$ nie przekracza $2000$ i żaden węzeł nie jest połączony z więcej niż trzema innymi węzłami.
• Testy 10-13: Żaden węzeł nie jest połączony z więcej niż trzema innymi węzłami.
• Testy 14-21: Brak dodatkowych ograniczeń.

Autor zadania: Avnith Vijayram