Varcolaci

Cerință

După 10 ore de cursuri, cei $N$ olimpîrliți se relaxează cu o rundă de “Vârcolaci”. După incidentul cu Dani și Simmy Jr din ziua 2, Oana a decis să introducă niște restricții în alegerea vârcolacilor. Mai exact, ea a ales $M$ perechi disjuncte de jucători pentru care nu este permis ca ambii să fie vârcolaci (poate fi doar unul din ei sau niciunul). În total, în joc trebuie să fie $K$ vârcolaci.

Ca de obicei, Oana “amestecă” rolurile așa cum dorește, și se întreabă în câte moduri poate alege cei $K$ vârcolaci, astfel încât toate cele $M$ restricții să fie respectate, modulo $10^9+7$.

Date de intrare

Pe prima linie se vor afla 3 numere $N$, $M$ și $K$ (numărul de jucători, numărul de restricții și numărul de vârcolaci).
Pe următoarele a $i$-a dintre următoarele $N$ linii se vor afla două valori $a_i$ și $b_i$ (cei doi jucători din restricția $i$).
Fiecare jucător apare în maxim o pereche!

Date de ieșire

Pe prima linie se va afișa numărul de moduri de a alege cei $K$ vârcolaci, modulo $10^9+7$.

Restricții și precizări

• $1 \le N \le 2\cdot 10^5$
• $1 \le K \le N-M$
• $0 \le M \le \frac{N}{2}$

Subtask-uri

Exemple

Exemplu

Intrare

4 1 2
1 3

Ieșire

5

Explicația exemplului

Cele 5 moduri de a alege vârcolacii sunt (perechea este subliniată, iar vârcolacii sunt cu bold):
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
Un exemplu de alegere incorectă este:
1 2 3 4

Exemplu

Intrare

4 2 2
1 4
2 3

Ieșire

4

Exemplu

Intrare

4 0 4

Ieșire

1