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.

#include <bits/stdc++.h>
using namespace std;

int n, m, k, p, a[10][10];

int fact(int n){
    if(n == 0)
        return 1;
    else
        return n * fact(n-1);
}

int main(){
    cin >> n >> m >> k >> p;
    int x, y;
    for(int i = 1; i <= k; ++i){
        cin >> x >> y;
        for(int j = 1; j <= m; ++j)
            a[x][j] = 1;
        for(int j = 1; j <= n; ++j)
            a[j][y] = 1;
    }
    int cnt = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(a[i][j] == 0)
                cnt++;
    if(cnt < p)
        cout << 0;
    else{
        cout << fact(cnt) / fact(cnt - p);
    }
}