#include <bits/stdc++.h>
#define ppc __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
const int P = 1e9 + 7;
int inv[21], vis[21], f[21], g[21];
int pre1[21], pre2[21], fac[21], ifac[21];
vector<int> G[21];
int C(int n, int m)
{
    if (m < 0 || m > n)
        return 0;
    return 1ll * fac[n] * ifac[n - m] % P * ifac[m] % P;
}
int bfs(int s, int st)
{
    queue<int> Q;
    Q.push(s);
    int cnt = 0;
    vis[s] = 1;
    while (Q.size())
    {
        int t = Q.front();
        Q.pop();
        cnt++;
        for (int son : G[t])
        {
            if (st >> (son - 1) & 1)
                continue;
            if (vis[son] == vis[t])
                return -1;
            if (!vis[son])
            {
                Q.push(son);
                vis[son] = 3 - vis[t];
            }
        }
    }
    return cnt;
}
int cal(int m, int st)
{
    vector<int> v;
    for (int j = 1; j <= m; j++)
    {
        vis[j] = 0;
    }
    for (int j = 1; j <= m; j++)
    {
        if (~st >> (j - 1) & 1 && !vis[j] && G[j].size())
        {
            v.push_back(bfs(j, st));
        }
    }
    int odd = 0, base = ppc(st);
    for (int x : v)
    {
        if (x == -1)
            return 0;
        odd += x & 1;
        base += x >> 1;
    }
    int ev = v.size() - odd;
    int ans = 0;
    for (int ex = 0; ex <= odd; ex++)
    {
        // base+ex ones on the left side
        // base+odd-ex ones ont the right side
        ans = (ans + 1ll * C(odd, ex) * f[base + ex] % P * g[base + odd - ex]) % P;
    }
    return 1ll * ans * (1 << ev) % P;
}
int main()
{
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    for (int i = 2; i <= 20; i++)
    {
        fac[i] = 1ll * fac[i - 1] * i % P;
        inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
    }
    int T;
    cin >> T;
    while (T--)
    {
        int n1, n2, m, k;
        cin >> n1 >> n2 >> m >> k;
        for (int i = 1; i <= m; i++)
            G[i].clear();
        for (int i = 1; i <= k; i++)
        {
            int a,b;
            cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        pre1[1] = pre2[1] = 1;
        for (int i = 2; i <= m; i++)
        {
            pre1[i] = 1ll * pre1[i - 1] * (n1 - i + 1) % P * inv[i - 1] % P;
            pre2[i] = 1ll * pre2[i - 1] * (n2 - i + 1) % P * inv[i - 1] % P;
        }
        int fr = 0;
        for (int i = 1; i <= m; i++)
            fr |= G[i].empty() << (i - 1);
        for (int m1 = 0; m1 + ppc(fr) <= m; m1++)
        {
            f[m1] = g[m1] = 0;
            for (int i = 0; i <= ppc(fr); i++)
            {
                f[m1] = (f[m1] + 1ll * C(ppc(fr), i) * pre1[m1 + i]) % P;
                g[m1] = (g[m1] + 1ll * C(ppc(fr), i) * pre2[m1 + i]) % P;
            }
        }
        int ans = 0;
        for (int i = 0; i < 1 << m; i++)
        {
            if (i & fr)
                continue;
            ans = (ans + cal(m, i)) % P;
        }
        cout << ans << endl;
    }
}