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

Poveste si cerinta...

Zaharel vrea sa plece intr-o excursie impreuna cu $K$ dintre cei $N$ prieteni (numerotati de la $1$ la $N$) ai sai. Desigur, nu poate lua cu el orice grup de $K$ prieteni, deoarece prezenta anumitor prieteni este conditionata de prezenta altora. Fiind un bun cunoscator al interactiunilor sociale din cadrul grupului sau de prieteni, Zaharel a facut o lista cu toate cele $M$ dependente existente in grupul sau: perechi de numere $i$ $j$ cu semnificatia ca prietenul cu numarul $i$ va veni in excursie, doar daca prietenul cu numarul $j$ vine si el. Vom numi o astfel de relatie {**dependenta directa**}.
Vom spune in continuare ca doi prieteni $i$ $j$ sunt in {**dependenta indirecta**} daca sunt in dependenta directa sau daca exista un sir de T≥1 numere $v1$, $v2$, ... , $vT$, astfel incat $i$ depinde direct de $v1$, $vp$ depinde direct de $vp+1$ (pentru 1≤ $p$≤ $T$) si $vT$ depinde direct de $j$.
La o analiza atenta a celor $M$ relatii Zaharel a observat ca exista o proprietate interesanta in cadrul grupului sau: pentru oricare trei prieteni distincti cu numere $i$ $j$ $k$, dacă $i$ depinde indirect de $j$ si $i$ depinde indirect de $k$, atunci $j$ depinde indirect de $k$, sau $k$ depinde indirect de $j$, sau ambele.
 
h2. Cerinta
 
Sa se scrie un program care determina in cate moduri poate alege Zaharel $K$ dintre cei $N$ prieteni ai lui pentru a merge in excursie, tinand cont de cele $M$ relatii de dependenta.

h2. Date de intrare

Fisierul de intrare $dep.in$ ...

Fisierul de intrare $dep.in$ va contine pe prima linie numerele $N$ $M$ $K$. Urmatoarele $M$ linii vor contine perechi de numere $i$ $j$ reprezentand dependentele directe.

h2. Date de iesire

In fisierul de iesire $dep.out$ ...

Fisierul de iesire $dep.out$ va contine pe prima linie un singur numar reprezentand în cate moduri poate alege Zaharel $K$ dintre cei $N$ prieteni. Rezultatul se va afişa modulo $666013$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1$ ≤ $K$ ≤ $N$ ≤ $256$
* $0$ ≤ $M$ ≤ $N*(N-1)/2$
* Pentru $20%$ din teste $N$ ≤ $25$
* Pentru $40%$ din teste nu vor exista dependente indirecte ciclice ( $i$ depinde indirect de $i$)
 

h2. Exemplu
table(example). |_. dep.in |_. dep.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|
h3. Explicatie

...

Zăhărel poate merge excursie fie cu prietenii 1 2 3, fie cu prietenii 3 4 5.
 
@!pagina?atasament!@

== include(page="template/taskfooter" task_id="dep") ==