== include(page="template/taskheader" task_id="zapezi2") ==

Mai Marii Altui Oraş se confruntă cu o iarnă prelungită. În Alt Oraş există $N$ intersecţii, numerotate de la $1$ la $N$, oricare două fiind conectate *direct* printr-o stradă bidirecţională. În condiţii meteorologice sumbre, Mai Marii trebuie să fie pregătiţi pentru situaţii de urgenţă. Numim reţea de urgenţă o submulţime de străzi neacoperite de zăpadă, de cardinal minim, care asigură existenţa unui drum direct sau indirect între oricare două intersecţii. Deocamdată există $K$ străzi înzăpezite. Mai Marii Altui Oraş ar dori să ştie câte reţele diferite de urgenţă se pot alcătui momentan *modulo 10^9^*.

Mai Marii Altui Oraş se confruntă cu o iarnă prelungită. În Alt Oraş există $N$ intersecţii, numerotate de la $1$ la $N$, oricare două fiind conectate *direct* printr-o stradă bidirecţională. În condiţii meteorologice sumbre, Mai Marii trebuie să fie pregătiţi pentru situaţii de urgenţă. Numim reţea de urgenţă o submulţime de străzi neacoperite de zăpadă, de cardinal minim, care asigură existenţa unui drum direct sau indirect între oricare două intersecţii. Deocamdată există $K$ străzi înzăpezite. Mai Marii Altui Oraş ar dori să ştie câte reţele de urgenţă se pot alcătui momentan *modulo 10^9*.

h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $zapezi2.out$ se vor afla $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător *modulo 10^9^*.

În fişierul de ieşire $zapezi2.out$ se vor afla $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător *modulo 10 ^ 9*.

h2. Restricţii
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 10.000$

* $1 ≤ K ≤ 16$

* $1 ≤ K ≤ 18$

h2. Exemplu