Rezolvare PBinfo #3703

În Hogwarts există o tablă de șah cu N linii și M coloane. Harry Potter a găsit plasate, de către Hagrid, T ture care apără fiecare linia și coloana pe care este așezată. El trebuie să plaseze în siguranță K pioni pe tablă, adică fără ca vreunul dintre ei să fie atacat de vreo tură. Tabla de șah din Hogwarts este specială deoarece în cadrul unei celule pot fi plasați chiar și mai mulți pioni simultan!

Cerința

Cunoscând toate aceste reguli, ajutați-l pe Harry Potter să determine în câte modalități poate plasa în siguranță toți cei K pioni pe tabla de șah.

Date de intrare

Fișierul de intrare potter.in conține pe prima linie patru numere naturale nenule N, M, T, K separate prin câte un spațiu, cu semnificațiile din enunț, iar pe următoarele T linii, perechi (i j) reprezentând linia și coloana unde este așezată fiecare tură.

Date de ieșire

Fișierul de ieșire potter.out conține un singur număr, reprezentând restul împărțirii la 1.000.000.007 a numărului de modalități distincte de a poziționa toți cei K pioni.

Restricții și precizări

• 1 ≤ N, M ≤ 2000
• 1 ≤ K ≤ 100.000
• 1 ≤ T ≤ N * M
• Două modalități de așezare sunt distincte dacă există cel puțin o celulă cu număr diferit de pioni

Exemplu:

potter.in

2 3 1 3
1 1

potter.out

4

Explicație

Pe tablă Harry Potter poate așeza în siguranță cei trei pioni în căsuțele (2,2) și (2,3). În cadrul fiecăreia el poate așeza 0, 1, 2, sau 3 pioni.