#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <int M>
struct modint {
    modint() : x(0) {}
    template <class T> modint(T n) { n %= M; if (n < 0) n += M; this->x = n; }

    modint & operator+=(const modint &r) { x += r.x; if (x >= M) x -= M; return *this; }
    modint & operator-=(const modint &r) { x -= r.x; if (x < 0) x += M; return *this; }
    modint & operator*=(const modint &r) { x = (int) ((long long) x * r.x % M); return *this; }

    modint & operator--() { if (--x == -1) x = M - 1; return *this; }
    modint & operator++() { if (++x == M) x = 0; return *this; }
    modint operator--(int) { modint t = *this; --*this; return t; }
    modint operator++(int) { modint t = *this; ++*this; return t; }

    modint operator-() const { return 0 - *this; }
    modint operator+() const { return *this; }

    modint power(long long k = M - 2) const {
        modint f = 1, p = *this;
        while (k > 0) {
            if (k & 1) f *= p;
            p *= p, k >>= 1;
        }
        return f;
    }

    int mod() const { return M; }

    friend modint operator+(modint l, const modint &r) { return l += r; }
    friend modint operator-(modint l, const modint &r) { return l -= r; }
    friend modint operator*(modint l, const modint &r) { return l *= r; }

    friend bool operator==(const modint &l, const modint &r) { return l.x == r.x; }
    friend bool operator!=(const modint &l, const modint &r) { return l.x != r.x; }

    friend ostream & operator<<(ostream &out, const modint &r) { return out << r.x; }

    int x;
};

using mint = modint<1000000000 + 7>;

struct Comb {
private:
    int n;
    std::vector<mint> _fac;
    std::vector<mint> _invfac;
    std::vector<mint> _inv;

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].power();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

public:

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }

    mint fact(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    mint ifact(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    mint inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    mint C(int n, int m) {
        return n < m || m < 0 ? 0 : fact(n) * ifact(m) * ifact(n - m);
    }
    mint A(int n, int m) {
        return n < m || m < 0 ? 0 : fact(n) * ifact(n - m);
    }
} comb;

struct DSU {
    vector<int> fa, sz;

    explicit DSU(int n) : fa(n), sz(n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }

    DSU() = default;

    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) {
            return false;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        fa[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

mint choose_slow(ll n, ll k) {
    if (n < k || k < 0 || n < 0) {
        return 0;
    }
    k = min(k, n - k);
    mint res = 1;
    for (int i = k; i >= 1; --i) {
        res *= (n - i + 1);
        res *= comb.inv(i);
    }
    return res;
}

void solve() {
    int N[2]{}, m, k;
    cin >> N[0] >> N[1] >> m >> k;
    vector<int> adj(m);
    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a] |= 1 << b;
        adj[b] |= 1 << a;
    }
    int M = 0;
    for (int i = 0; i < m; ++i) {
        if (adj[i]) {
            M |= 1 << i;
        }
    }
//    cout << M << endl;
    const int additional = m - __builtin_popcount(M);
    vector prob(m + 1, vector<mint>(m + 1));
    vector<int> color(m, -1);
    vector<array<int, 2>> sizes(m);
    for (int exactly = 0; exactly <= M; exactly = (exactly + 1) & M) {
        fill(color.begin(), color.end(), -1);
        int notUsed = exactly;
        DSU dsu(m);
//        if (exactly == 2 + 4) {
//            cout << "here!" << endl;
//        }
        for (int z = exactly; z > 0; z -= z & -z) {
            int id = __lg(z & -z);
            if (color[id] == -1) {
                color[id] = 0;
                auto dfs = [&](auto self, int v) -> void {
                    notUsed -= (notUsed & (1 << v));
                    int to = adj[v];
                    while (true) {
                        to = notUsed & to;
                        if (to == 0) {
                            break;
                        }
                        int nxt = __lg(to & -to);
                        dsu.unite(nxt, v);
                        color[nxt] = color[v] ^ 1;
                        self(self, nxt);
                        to -= to & -to;
                    }
                };
                dfs(dfs, id);
            }
        }
        int zero = 0, one = 0;
        for (int i = 0; i < m; ++i) {
            if (color[i] != -1) {
                (color[i] ? one : zero) |= 1 << i;
            }
        }
        bool yay = true;
        for (int i = 0; i < m; ++i) {
            sizes[i][0] = sizes[i][1] = 0;
        }
        for (int i = 0; i < m && yay; ++i) {
            if (color[i] != -1) {
                if (adj[i] & (color[i] ? one : zero)) {
                    yay = false;
                    break;
                }
                sizes[dsu.find(i)][color[i]] += 1;
            }
        }
//        if (exactly == 6) {
//            cout << "another: " << yay << endl;
//        }
        if (yay) {
//            cout << exactly << endl;
            vector<mint> dp(1);
            dp[0] = 1;
            int sumSizes = 0;
            vector<vector<int>> orders(m + 1);
            for (int i = 0; i < m; ++i) {
                if (color[i] != -1 && dsu.fa[i] == i) {
                    orders[max(sizes[i][0], sizes[i][1])].push_back(i);
                }
            }
            for (auto &f : orders) {
                for (auto &i : f) {
                    auto [z, o] = sizes[i];
                    int nxtSum = sumSizes + max(z, o);
                    vector<mint> dq(nxtSum + 1);
                    for (int t : {z, o}) {
                        for (int i = 0; i < dp.size(); ++i) {
                            dq[i + t] += dp[i];
                        }
                    }
                    swap(dp, dq);
                    sumSizes = nxtSum;
                }
            }
            int sumAll = __builtin_popcount(exactly);
            int both = __builtin_popcount(M) - sumAll;
            for (int x = 0; x <= sumSizes; ++x) {
                if (dp[x].x) {
                    prob[x + both][sumAll - x + both] += dp[x];
                }
            }
        }
        if (exactly == M) {
            break;
        }
    }
    vector dp(m + 1, vector<mint>(m + 1));
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (prob[i][j].x == 0) {
                continue;
            }
            for (int ax = 0; ax <= additional; ++ax) {
                for (int ay = 0; ay <= additional; ++ay) {
                    dp[i + ax][j + ay] += prob[i][j] * comb.C(additional, ax) * comb.C(additional, ay);
                }
            }
        }
    }
    mint answer = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (dp[i][j].x) {
                answer += dp[i][j] * choose_slow(N[0] - i + (i - 1), i - 1) * choose_slow(N[1] - j + (j - 1), j - 1);
            }
        }
    }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test = 1;
    cin >> test;

    while (test--) {
        solve();
    }

    return 0;
}