legat

Lensu a fost provocat de Buzdi și Cosmin să joace un joc numit "Legat". Acest joc are loc într-un palat cu $N$ camere, numerotate de la 1 la $N$, conectate prin $M$ uși unidirecționale, astfel încât nu poți ajunge din nou într-o cameră în care ai fost deja pe parcursul jocului. Jocul acesta este format din $N$ runde, ce se desfașoară în felul următor:

• La runda i, Lensu va fi băgat într-o cameră de start diferită față de cele din ultimele i - 1 runde și va fi legat la ochi.
• El trebuie să intre prin cel mult $L$ uși.
• Pe parcursul jocului, Lensu poate spune "STOP", moment în care, dacă acesta se află în camera $N$, el este câștigător si jocul se termina. Dacă acesta nu se află în camera $N$, atunci el va trece la următoarea rundă.

Dacă Lensu nu este câștigător după cele $N$ runde, acesta a pierdut jocul.

Cerința

Lensu vrea sa pună un pariu cu Buzdi și Cosmin. Pentru a ști cât să parieze, acesta vrea să afle care este probabilitatea de a câștiga jocul.

Date de intrare

Pe prima linie se găsesc numerele naturale $N$, $M$ și $L$. Pe următoarele $M$ linii se vor regăsi câte două numere naturale x y, separate printr-un spațiu, cu semnificația că există o ușă care duce din camera x în camera y.

Date de ieșire

Se va afișa un singur număr natural $P$, reprezentând probabilitatea ca Lensu să câștige jocul. Acest număr va fi afișat modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• $1 \leq M \leq 500 \ 000$
• $1 \leq L \leq 100$
• $P = \frac{nr \ cazuri \ favorabile}{nr \ cazuri \ posibile}$
• Probabilitatea $P$ este o fracție $\frac{a}{b}$ exprimată ca $a \times b^{-1}$, unde $b^{-1}$ este inversul modular a lui $b$ modulo $1 \ 000 \ 000 \ 007$.
• Lensu nu joacă neapărat optim, el știe doar câte uși a deschis.
• Pentru 21 de puncte, $2 \leq N \leq 100, 1 \leq M \leq 200$

Exemplul

stdin

8 10 3
6 2
4 2
2 8
3 8
2 3
1 3
7 4
4 5
1 6
1 7

stdout

305555558

Explicație

Există $11$ situații în care acesta ajunge în camera $8$ și spune "STOP" intrând prin maxim $3$ uși. În fiecare situație, el va trece în ordine prin camerele:

• $(8)$
• $(2, 8)$
• $(3, 8)$
• $(1, 3, 8)$
• $(6, 2, 8)$
• $(4, 2, 8)$
• $(2, 3, 8)$
• $(6, 2, 3, 8)$
• $(4, 2, 3, 8)$
• $(7, 4, 2, 8)$
• $(1, 6, 2, 8)$

Numărul total de situații în care intră prin maxim $3$ uși și spune "STOP" în una dintre camere este $36$. Astfel, probabilitatea ca Lensu să câștige este de $\frac{11}{36}$, iar $\frac{11}{36}$ modulo $1 \ 000 \ 000 \ 007$ = $305555558$