#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
ll n1,n2,m,k,M;
ll F1[1<<21],F2[1<<21];
const ll MOD = 1e9+7;
ll binpow(ll a,ll b){
    ll ans = 1;
    ll mul = a;
    while(b){
        if(b&1LL) ans = ans*mul%MOD;
        mul = mul*mul%MOD;
        b>>=1LL;
    }
    return ans;
}
ll f2(ll m1){
    if(F2[m1] != -1) return F2[m1];
    ll b = m-m1-1;
    ll a = n2-1+m-M;
    if(a <0 || b <0 ||a-b < 0) return 0;
    ll mul = 1;
    ll div = 1;
    for(ll i = a-b+1; i <= a;i++) mul = mul*i%MOD;
    for(ll i = 1; i <= b;i++) div = div*i%MOD;
    div = binpow(div,MOD-2);
    return F2[m1]=mul*div%MOD;
}
ll f1(ll m2){
    if(F1[m2] != -1) return F1[m2];
    ll b = m-m2-1;
    ll a = n1-1+m-M;
    if(a <0 || b <0 ||a-b < 0) return 0;
    ll mul = 1;
    ll div = 1;
    for(ll i = a-b+1; i <= a;i++) mul = mul*i%MOD;
    for(ll i = 1; i <= b;i++) div = div*i%MOD;
    div = binpow(div,MOD-2);
    return F1[m2]=mul*div%MOD;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){

        cin >> n1 >> n2 >> m >> k;
        vector<pair<ll,ll>> v(k);
        FOR(i,0,(1<<m)) F1[i] = -1,F2[i] = -1;
        FOR(i,0,k) cin >> v[i].first >> v[i].second;
        int mask = 0;
        FOR(i,0,k){
            mask |=(1<<(v[i].first-1));
            mask |=(1<<(v[i].second-1));
        }
        M = __builtin_popcount(mask);
        vector<ll> evil(m);
        int avoid = 0;
        for(int i = 0; i < m;i++){
            for (int j = 0; j < k; j++){
                if(v[j].first == v[j].second) avoid |= (1<<(v[j].first-1));
                else if(v[j].first-1 == i) evil[i] |= (1<<(v[j].second-1));
                else if(v[j].second-1== i) evil[i] |= (1<<(v[j].first-1));
            }
        }
        //m1
        ll ans = 0;

        for(int i = mask;; i = (i-1)&mask){
            if((i&avoid)!=0){
                if(i == 0)break;
                else continue;
            }
            int comp = mask^i;
            int ev = 0;
            for(int j = 0; j < m; j++){
                if(i&(1<<j)) ev |= evil[j];
            }
            if((ev&comp) != ev){
                if(i == 0)break;
                else continue;
            }
            ll temp = 0;
            for(int j = comp;; j= (j-1)&comp){
                if((j&avoid)!=0){
                if(j == 0)break;
                else continue;
            }
                int co = mask^j;
                ev = 0;
                for(int kk = 0; kk < m; kk++){
                    if(j&(1<<kk)) ev |= evil[kk];
                }
                if((ev&co) != ev){
                    if(j == 0)break;
                    else continue;
                }
                // cout << i<<" "<<j<<'\n';
                temp +=f1(__builtin_popcount(j));
                if(temp >= MOD) temp -=MOD;
                if(j == 0) break;
            }
            ans += f2(__builtin_popcount(i))*temp;
            ans %=MOD;
            if(i == 0) break;
        }
        cout <<ans <<'\n';

    }
}