#include <bits/stdc++.h>
#define ppc __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
const int P = 1e9 + 7;
int inv[21], f[21], g[21];
int fr;
int pre1[21], pre2[21], fac[21], ifac[21];
struct node
{
    int fa[21], val[21], sz[21];
    int Find(int x)
    {
        if (x != fa[x])
        {
            int t = fa[x];
            fa[x] = Find(fa[x]);
            val[x] ^= val[t];
        }
        return fa[x];
    }
} info[1 << 20];
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 cal(int m, int st)
{
    vector<int> v;
    if (st)
    {
        int nxt = st - (st & -st);
        int cur = ctz(st) + 1;
        info[st] = info[nxt];
        info[st].sz[cur] = 1;
        info[st].fa[cur] = cur;
        for (int son : G[cur])
        {
            if (~st >> (son - 1) & 1)
                continue;
            int tmp = info[st].Find(son);
            if (tmp == cur)
            {
                if (info[st].val[son] == info[st].val[cur])
                    return 0;
            }
            else
            {
                info[st].val[tmp] ^= info[st].val[cur] ^ 1;
                info[st].fa[tmp] = cur;
                info[st].sz[cur] += info[st].sz[tmp];
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (st >> (i - 1) & 1 && info[st].fa[i] == i)
            v.push_back(info[st].sz[i]);
    }
    int odd = 0, base = m - ppc(st) - ppc(fr);
    for (int x : v)
    {
        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 ans * (1ll << 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;
        }
        fr = 0;
        for (int i = 1; i <= m; i++)
            if (G[i].empty())
                fr |= 1 << (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 k = m; ~k; k--)
            for (int i = 0; i < 1 << m; i++)
            {
                if (ppc(i) != k)
                    continue;
                if (i & fr)
                    continue;
                int msk = (1 << m) - 1;
                ans = (ans + cal(m, ~i & msk & ~fr)) % P;
            }
        cout << ans << endl;
    }
}