ture

Ture

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

Poveste si cerinta...

Gigel are o tabla de sah cu $N$ linii si $M$ coloane. El vrea sa aseze pe tabla $K$ ture astfel incat acestea sa nu se atace intre ele ( Spunem ca doua ture se ataca daca ele se afla pe aceeasi linie sau pe aceeasi coloana). Pentru a face lucrurile mai interesante Gigel a marcat anumite casute in care nu poate aseza nici o tura si acum vrea sa stie in cate moduri poate aseza turele.
 
h2. Cerinta
 
Ajutati-l pe Gigel sa gaseasca numarul de posibilitati in care poate aseza cele $K$ ture.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $ture.in$  sunt scrise trei numere: {$N$}, $M$  si $K$ separate printr-un singur spatiu. Pe a doua linie se afla $P$ numarul de casute marcate de Gigel. Urmeaza apoi $P$ linii cu cate doua numere {$x$}, $y$ cu semnificatia ca Gigel a marcat casuta de pe linia $x$ si coloana {$y$}.

h2. Date de iesire

...

Prima linie a fisierului $ture.out$ va contine numarul de posibilitati de amplasare a turelor pe tabla de sah.

h2. Restrictii

... ≤ ...

* {$0 ≤ N*M ≤ 250$}
* {$0 ≤ K ≤ 100$}
* {$0 ≤ P ≤ N*M$}
 

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

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

| 3 3 3
1
2 2
| 4

|

h3. Explicatie
 
...
 

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

1505