dep

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 \geq 1$ numere $v_1, v_2, \dots, v_T$, astfel încât $i$ depinde direct de $v_1$, $v_p$ depinde direct de $v_{p+1}$ (pentru $1 \leq p < T$) şi $v_T$ 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 $666 \ 013$.

Restricții și precizări

• $1 \leq K \leq N \leq 256$
• $0 \leq M \leq \frac{N \cdot (N-1)}{2}$
• Pentru $20\%$ din teste $N \leq 25$
• Pentru $40\%$ din teste nu vor exista dependenţe indirecte ciclice ($i$ depinde indirect de $i$)

Exemplu

dep.in

5 8 3
1 2
2 1
1 3
2 3
4 5
5 4
4 3
5 3

dep.out

2

Explicație

Zăhărel poate merge excursie fie cu prietenii $1 \ 2 \ 3$, fie cu prietenii $3 \ 4 \ 5$.