Problema Patagonia

Patagonia este o întinsă regiune din America de Sud și este cunoscută pentru solurile fertile și un climat favorabil agriculturii, motiv pentru care habitatul animalelor native s-a redus considerabil și poate fi reprezentat printr-o zonă dreptunghiulară cu lățimea de N metri și lungimea de M metri, pe care o impărțim în parcele de dimensiune unitară, asemenea unei matrici. Aici locuieste o populatie formata din V vulturi, fiecare avand cuibul într-o parcela unitară și o populație de K iepuri. Fiecare vultur vânează iepuri aflati pe linia sau pe coloana pe care se află cuibul lor, aceste zone fiind unele nesigure, toate celelalte zone sunt sigure. Iepurii vor să locuiască doar în zone sigure.

Cerință

Cunoscând aceste reguli, ajutați iepurii să afle numărul de zone sigure, și modul în care își pot face case, știind că pot locui oricâți iepuri în aceeași zonă.

Date de intrare

Fișierul de intrare patagonia.in conține pe prima linie 5 numere naturale C N M V K cu semnificațiile din enunț, iar pe următoarele V linii câte o pereche de valori x y cu semnificația că un vultur are cuib în parcela de pe linia x și coloana y.

Date de ieșire

Daca valoarea lui C este 1, atunci fișierul de ieșire patagonia.out va conține o singură valoare reprezentând numărul zonelor sigure din matrice, iar dacă valoarea lui C este 2, se va afișa numărul de moduri în care iepurii își pot face case. Deoarece această valoare poate fi extrem de mare, iepurii sunt fericiți cu restul impărțirii la 666013.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• 1 ≤ K ≤ 100.000
• 1 ≤ V ≤ N × M
• Pentru 20% dintre teste, C = 1, iar pentru restul de 80%, C = 2
• Pentru 50% dintre teste, atât la C = 1 cât și la C = 2, N și M sunt ≤ 500
• Două modalități de așezare sunt distincte dacă există cel puțin o zonă cu număr diferit de iepuri
• Presupunem că toți iepurii sunt la fel, adică nu contează care iepuri vor locui într-o anumită zonă, ci doar câți

Exemple