Zăhărel vrea să plece într-o excursie împreuna cu K dintre cei N prieteni (numerotaţi de la 1 la N) ai săi. Desigur, nu poate lua cu el orice grup de K prieteni, deoarece prezenţa anumitor prieteni este condiţionată de prezenţa altora. Fiind un bun cunoscător al interacţiunilor sociale din cadrul grupului său de prieteni, Zăhărel a făcut o listă cu toate cele M dependenţe existente în grupul său: perechi de numere i j cu semnificaţia că prietenul cu numărul i va veni în excursie, doar dacă prietenul cu numărul j vine şi el. Vom numi o astfel de relaţie dependenţă directă.
Vom spune în continuare că doi prieteni i j sunt în dependenţă indirectă dacă sunt în dependenţă directă sau dacă există un şir de T≥1 numere v1 v2 ... vT, astfel încât i depinde direct de v1, vp depinde direct de vp+1 (pentru 1≤p<T) şi vT depinde direct de j.
La o analiză atentă a celor M relaţii Zăhărel a observat ca există o proprietate interesantă în cadrul grupului său: pentru oricare trei prieteni distincţi cu numere i j k, dacă i depinde indirect de j şi i depinde indirect de k, atunci j depinde indirect de k, sau k depinde indirect de j, sau ambele.
Cerinţă
Să se scrie un program care determină în câte moduri poate alege Zăhărel K dintre cei N prieteni ai lui pentru a merge în excursie, ţinând cont de cele M relaţii de dependenţă.
Date de intrare
Fişierul de intrare dep.in va conţine pe prima linie numerele N M K. Următoarele M linii vor conţine perechi de numere i j reprezentând dependenţele directe.
Date de ieşire
Fişierul de ieşire dep.out va conţine pe prima linie un singur număr reprezentând în câte moduri poate alege Zăhărel K dintre cei N prieteni. Rezultatul se va afişa modulo 666013.
Restricţii
1 ≤ K ≤ N ≤ 256
0 ≤ M ≤ N*(N-1)/2
Pentru 20% din teste N ≤ 25
Pentru 40% din teste nu vor exista dependenţe indirecte ciclice (i depinde indirect de i)
Exemple
dep.in
dep.out
Explicaţii
5 8 3
1 2
2 1
1 3
2 3
4 5
5 4
4 3
5 3
2
Zăhărel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.
