#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define data dataa
using LL=long long;
using ULL=unsigned long long;
using LD=long double;
const int MOD=int(1e9)+7;
int inv[50],ans[1<<20],a[410],n1,n2,k,m;
void update(int&x,int y){x=(x+y)%MOD;}
int mypow(int x,int n){int res=1;for(;n;n>>=1,x=LL(x)*x%MOD)if(n&1)res=LL(res)*x%MOD;return res;}
int C(int n,int m)
{
    int res=1;
    for(int i=n;i>=n-m+1;i--)res=LL(res)*i%MOD;
    rep(i,m)res=LL(res)*inv[i]%MOD;
    return res;
}
int cal(int n,int m)
{
    if(n<m)return 0;
    return C(n-1,m-1);
}
int main()
{
    int T;
    inv[0]=1;
    rep(i,20)inv[i]=LL(inv[i-1])*mypow(i,MOD-2)%MOD;
    for(scanf("%d",&T);T--;)
    {
        scanf("%d%d%d%d",&n1,&n2,&m,&k);
        rep(i,k)
        {
            int x,y;scanf("%d%d",&x,&y);
            a[i]=(1<<(x-1))|(1<<(y-1));
        }
        for(int i=0;i<(1<<m);i++)
        {
            bool flag=1;
            rep(j,k)if(!(a[j]&i)){flag=0;break;}
            ans[i]=flag*cal(n2,__builtin_popcount(i));
        }
        rep(i,m)rep(j,(1<<m))if(!((j>>(i-1))&1))update(ans[j],ans[j^(1<<(i-1))]);
        int allans=0;
        for(int i=0;i<(1<<m);i++)
        {
            bool flag=1;
            int msk=0;
            rep(j,k)
            {
                int x=a[j]&i;
                if(!x){flag=0;break;}
                if((a[j]&-a[j])==a[j]){msk|=a[j];continue;}
                if((x&-x)==x)msk|=a[j]^x;
            }
            if(!flag)continue;
            update(allans,LL(cal(n1,__builtin_popcount(i)))*ans[msk]%MOD);
        }
        printf("%d\n",allans);
    }
    return 0;
}