Busy Beaver znów sieje chaos na targu! Tym razem rozpoczyna bitwę na jedzenie między straganami.

Stragany są ponumerowane od $1$ do $N$ i połączone $N - 1$ drogami, tworząc drzewo. Innymi słowy, można podróżować z dowolnego straganu do każdego innego, podążając drogami, i istnieje dokładnie jedna prosta ścieżka między dowolnymi dwoma straganami.

Busy Beaver przypisuje każdy stragan do Drużyny Ziemniaka (Team Potato) lub Drużyny Pomidora (Team Tomato) w następujący sposób:

• Zaczyna od straganu $1$, podróżuje drogami, odwiedza każdy stragan i ostatecznie wraca do straganu $1$. Spośród wszystkich takich tras wybiera tę o minimalnej możliwej całkowitej liczbie przebytych dróg.
• Stragan $1$ jest przypisany do Drużyny Ziemniaka.
• Ilekroć Busy Beaver odwiedza stragan po raz pierwszy (inny niż stragan $1$), natychmiast przypisuje go do jednej z dwóch drużyn. Aby zachować sprawiedliwość, zmienia drużynę przy każdym nowym przypisaniu straganu. Oznacza to, że jeśli ostatnio przypisany stragan należał do Drużyny Ziemniaka, to następny nowo odwiedzony stragan musi zostać przypisany do Drużyny Pomidora i na odwrót.

Twoim zadaniem jest zliczenie liczby możliwych przypisań do drużyn. Zauważ, że różne trasy o minimalnej długości mogą prowadzić do tego samego końcowego przypisania; takie przypisania należy liczyć tylko raz. Ponieważ wynik może być ogromny, wyprowadź go modulo $10^9 + 7$.

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^4$) — liczbę zestawów danych.

Pierwsza linia każdego zestawu danych zawiera pojedynczą liczbę całkowitą $N$ ($2 \le N \le 10^5$).

Każda z kolejnych $N - 1$ linii zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le N, u \neq v$), wskazujące, że istnieje droga między straganami $u$ oraz $v$.

Suma $N$ we wszystkich zestawach danych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wyprowadź pojedynczą liczbę całkowitą: liczbę możliwych końcowych przypisań do drużyn modulo $10^9 + 7$.

Podzadania

Istnieją dwa podzadania dla tego problemu:

• (10 punktów): Stragany tworzą graf gwiazdy zakorzeniony w straganie $1$. Dokładniej, stragan $1$ ma $N - 1$ połączonych z nim dróg.
• (20 punktów): Stragany tworzą drzewo binarne zakorzenione w straganie $1$. Dokładniej, stragan $1$ ma co najwyżej $2$ połączone z nim drogi, a każdy inny stragan ma co najwyżej $3$ połączone z nim drogi.
• (70 punktów): Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

2
20
8
12

Uwagi

Próbka zawiera 4 zestawy danych:

• Zestaw danych 1 spełnia drugie podzadanie (drzewo binarne).
• Zestaw danych 2 spełnia pierwsze podzadanie (graf gwiazdy).
• Zestaw danych 3 spełnia drugie podzadanie (drzewo binarne).
• Zestaw danych 4 spełnia trzecie podzadanie (brak dodatkowych ograniczeń).

W pierwszym zestawie danych jedno z możliwych przypisań do drużyn pokazano poniżej.

Jedna trasa o minimalnej długości to: $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$.

Jej całkowita długość wynosi $6$, co jest najmniejszą możliwą wartością dla trasy, która zaczyna się w straganie $1$, odwiedza każdy stragan i wraca do straganu $1$.

Stragany są następnie przypisywane w kolejności, w jakiej są odwiedzane po raz pierwszy:

• Stragan $1$ jest przypisany do Drużyny Ziemniaka.
• Stragan $2$ jest przypisany do Drużyny Pomidora.
• Stragan $3$ jest przypisany do Drużyny Ziemniaka.
• Stragan $4$ jest przypisany do Drużyny Pomidora.

Drugie możliwe przypisanie do drużyn uzyskuje się poprzez odwiedzenie straganu $4$ przed straganem $3$, co zamienia ich drużyny. Dlatego całkowita liczba możliwych przypisań do drużyn wynosi $2$.