#include <bits/stdc++.h>

using namespace std;
#define int long long int
#define pb push_back
#define sz(x) (int)(x.size())
const int N = 25, MSK = (1ll << 16), INF = 1e9;

int n, m, k, p, dp[N][MSK], a[N][N];

/// dp[i][mask] = numarul de modalitati de a plasa __builtin_popcount(mask) ture in prefixul i
/// __builtin_popcount(mask) <= i si __builtin_popcount(mask) <= k
/// dp[i][mask] = dp[i - 1][mask ^ (1ll << pozitie)], pozitie >= 1 && pozitie <= m
/// si a[i][pozitie] == 0

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    freopen("ture.in", "r", stdin);
    freopen("ture.out", "w", stdout);
    cin >> n >> m >> k >> p;
    if (m > n) {
        swap(m, n);
    }
    for (int i = 1; i <= p; i++) {
        int x, y;
        cin >> x >> y;
        --y;
        a[x][y] = 1;
    }
    dp[0][0] = 1;
    for (int mask = 0; mask < (1ll << m); mask++) {
        if (__builtin_popcountll(mask) <= k) {
            for (int i = 1; i <= n; i++) {
                if (__builtin_popcountll(mask) <= i) {
                    dp[i][mask] = dp[i - 1][mask]; /// daca nu pun tura pe linia/coloana i
                    for (int j = 0; j < m; j++) {
                        if (mask & (1ll << j)) {
                            if (a[i][j] == 0) {
                                dp[i][mask] += dp[i - 1][mask ^ (1ll << j)];
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int mask = 0; mask < (1ll << m); mask++) {
        if (__builtin_popcountll(mask) == k) {
            ans += dp[n][mask];
        }
    }
    cout << ans;
}