Peste 3700 de ani lumea a devenit dreptunghiulară, este formată n x m
zone și este stăpânită de un rege care are o armată formată din q
soldați. În regat se află k
turnuri de piatră, ostile armatei regelui, la coordonate cunoscute; fiecare turn atacă zonele de pe linia și coloana sa.
Cerința
Regele dorește să afle în câte moduri poate plasa soldații în zonele fără turnuri ale regatului astfel încât aceștia să nu fie atacați de turnuri.
Date de intrare
Programul citește de la tastatură dimensiunile n
și m
ale regatului, numărul de turnuri k
și numărul de soldați q
. Pe următoarele k
linii se află câte două valori, reprezentând coordonatele turnurilor.
Date de ieșire
Programul va afișa pe ecran numărul p
, reprezentând numărul de moduri în care pot fi plasați soldații regelui.
Restricții și precizări
1 ≤ n , m ≤ 4
1 ≤ q , k ≤ n*m
- în cazul în care nu există niciun mod de plasare a soldaților se va afișa
0
- soldații sunt diferiți între ei; două moduri de plasare a soldaților pot să folosească aceleași zone, dar să fie diferite prin ordinea în care sunt plasați soldații în aceste zone.
Exemplu 1:
Intrare
3 3 1 1 2 2
Ieșire
4
Explicație
Zonele neatacate de turnuri au coordonatele (1,1)
, (1,3)
, (3,1)
, (3,3)
.
Exemplu 2:
Intrare
4 4 1 9 1 1
Ieșire
362880
Precizare
Acesta este cel mai mare test.
Exemplu 3:
Intrare
3 3 3 4 1 1 2 2 3 3
Ieșire
0
Explicație
Nu au rămas destule zone neatacate de turnuri.