7. Šibalské sny

Súhvezdia sú nudné. Existujú si na oblohe a veľa toho nenarozprávajú. Niektoré dvojice hviezd v súhvezdí sú spojené čiarou, vraj, aby ľuďom viac niečo pripomínali.

Sem-tam sa ale aj také súhvezdie potrebuje ponaťahovať. Hadonoš¹ rád sníva. Rozmýšľa, ako rôzne by sa mohol ponaťahovať, keby bol nejakým iným súhvezdím. Vždy, keď sa mu takto prisní, že je iným súhvezdím, prudko sa zobudí a začne počítať, koľkými rôznymi spôsobmi by vedel svoje hviezdy usporiadať. Nemá ale príliš veľký mozog a tak sa mu snívajú iba samé spojité acyklické konfigurácie.

Nie je to ale iba tak. Nebyť súhvezdí, Kolumbus by nedoplával do Ameriky², Cook by zablúdil už pri Dubline a Krtko by nevedel trafiť na správne sústredenie. Nemôžu sa teda naťahovať len tak, ako sa im zachce. Musia sa ľuďom javiť nezmenené.

Úloha

Hadonoš vám postupne popíše každý jeho sen. Každý sen je jedno súhvezdie, teda hviezdy a čiary, ktorými sú niektoré dvojice hviezd prepojené. Každé prisnené súhvezdie tvorí strom. Každá hviezda má svoje číslo, hviezdy sú teda rozoznateľné.

Hadonoš po zobudení potrebuje vyrátať, koľkými spôsobmi sa dajú v prisnenom súhvezdí preusporiadať hviezdy tak, aby platilo:

• Hviezda číslo \(0\) nezmení svoju pozíciu
• Množina pozícií na oblohe, ktoré boli obsadené hviezdami súhvezdia je pred usporiadaním rovnaká ako po ňom
• Ak pred usporiadaním boli čiarou spojené hviezdy \(a\) a \(b\), tak sú spojené čiarou aj po usporiadaní

Každé súhvezdie teda tvorí strom zakorenený v \(0\).

Bez odpovede Hadonoš znovu nezaspí a na zajtrajšiu skúšku z astronómie príde unavený. Uspite ho!

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(T\) – počet Hadonošovych snov. Platí \(1 \leq T \leq 10\). Nasleduje \(T\) popisov snov.

Popis sna začína riadkom s číslom \(n\) – počet hviezd v prisnenom súhvezdí. Platí \(3 \leq n \leq 10\,000\). Nasleduje \(n - 1\) riadkov. Na \(i\)-tom z nich sa nachádzajú čísla \(a_i\), \(b_i\) oddelené medzerou. Tie hovoria, že v prisnenom súhvezdí sú čiarou spojené hviezdy \(a_i\) a \(b_i\). Platí \(0 \leq a_i, b_i < n\).

Každé prisnené súhvezdie tvorí strom.

Formát výstupu

Pre \(i\)-ty sen vypíšte na \(i\)-ty riadok výstupu jedno číslo – počet rôznych usporiadaní hviezd \(i\)-teho prisneného súhvezdia spĺňajúcich vyššie popísané požiadavky. Keďže odpoveď môže byť veľmi veľká, vypisujte ju modulo \(10^9 + 7\).

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklad

Input:

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

Output:

2
8

V prvom súhvezdí sú vyhovujúce dve možnosti. Prvou je nespraviť žiadnu zmenu, druhou je vymeniť vrcholy 3 a 4. V druhom súhvezdí je jednou z možností napríklad vymeniť koreňu ľavý a pravý podstrom a naviac vymeniť vrcholy 5 a 6.