#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e9+7;
int n1,n2,m,k;
int a[405],b[405];
int g1[25],g2[25];
int l[25];
int c[25][25];
int h[(1<<20)+5];
int jc[25];
int fa[45],vis[45];
int sz[45];
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y)return;
    fa[x]=y;
    sz[y]+=sz[x];
}
int qpow(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y&1)ans=ans*x%M;
        y>>=1;
        x=x*x%M;
    }
    return ans;
}
int C(int n,int m)
{
    if(m<0||m>n)return 0;
    if(n<=20&&m<=20)return c[n][m];
    int ans=1;
    for(int i=0;i<m;i++)
        ans=ans*(n-i)%M*qpow(i+1,M-2)%M;
    return ans;
}
void sol()
{
    cin>>n1>>n2>>m>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>a[i]>>b[i];
        a[i]--;
        b[i]--;
    }
    jc[0]=1;
    for(int i=1;i<=m;i++)
        jc[i]=i*jc[i-1]%M;
    g1[0]=g2[0]=0;
    for(int i=1;i<=m;i++)
    {
        g1[i]=C(n1-1,i-1);
        g2[i]=C(n2-1,i-1);
        //cerr<<i<<" "<<g1[i]<<" "<<g2[i]<<'\n';
    }
    int ans=0;
    for(int sta=0;sta<(1<<m);sta++)
    {
        for(int i=0;i<2*m;i++)
        {
            fa[i]=i,vis[i]=0;
            if(i<m)sz[i]=1;
            else sz[i]=0;
        }
        int B=0;
        for(int i=1;i<=k;i++)
        {
            if(((sta>>a[i])&1)&&((sta>>b[i])&1))
                continue;
            if((sta>>a[i])&1)
                B|=(1<<b[i]);
            else if((sta>>b[i])&1)
                B|=(1<<a[i]);
            else
            {
                B|=(1<<b[i]);
                B|=(1<<a[i]);
                merge(a[i],b[i]+m);
                merge(a[i]+m,b[i]);
            }
        }
        for(int i=0;i<=m;i++)
            l[i]=0;
        l[0]=1;
        bool fl=0;
        for(int i=0;i<m;i++)
        {
            if(!((sta>>i)&1))
            {
                int u=find(i),v=find(i+m);
                if(u==v)
                {
                    fl=1;
                    break;
                }
                if(vis[u]||vis[v])continue;
                vis[u]=vis[v]=1;
                //cerr<<sz[u]<<" "<<sz[v]<<'\n';
                for(int j=m;j>=0;j--)
                {
                    int t=0;
                    if(j>=sz[u])t+=l[j-sz[u]];
                    if(j>=sz[v])t+=l[j-sz[v]];
                    l[j]=t%M;
                }
            }
        }
        if(fl)continue;
        B=h[B];
        int A=h[sta];
        for(int i=A+B;i<=m;i++)
        {
            for(int j=0;j<=m-A;j++)
            {
                ans=(ans+C(m-A-B,m-i)*l[j]%M*g1[A+j]%M*g2[i-j])%M;
            }
        }
        //cerr<<sta<<" "<<ans<<" "<<g2[2]<<" "<<g1[2]<<'\n';
    }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=0;i<=20;i++)
        c[i][0]=1;
    for(int i=1;i<=20;i++)
        for(int j=1;j<=20;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;
    for(int i=1;i<(1<<20);i++)
        h[i]=h[i-(i&-i)]+1;
    int T=1;
    cin>>T;
    while(T--)
    {
        sol();
    }
}