#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define rep2(i, l, r) for(ll i = (l); i < (r); ++i)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;

bool chmin(auto &a, auto b) {return a > b ? a = b, 1 : 0;}
bool chmax(auto &a, auto b) {return a < b ? a = b, 1 : 0;}

struct IOS {
  IOS() {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
} iosetup;


template<class T>
void print(vector<T> a) {
  for(auto x : a) cout << x << ' ';
  cout << endl;
}

void print(auto x) {
  cout << x << endl;
}

template<class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cout << head << ' ';
  print(forward<Tail>(tail)...);
}

const ll MOD = 1e9 + 7;

ll modpow(ll x, ll k, ll m = MOD) {
  ll v = 1;
  while(k) {
    if(k & 1) v = v * x % m;
    x = x * x % m;
    k >>= 1;
  }
  return v;
}

int len = 2e5;
vll fac, finv;

void precalc(ll m = MOD) {
  fac.assign(len, 1), finv.assign(len, 1);
  rep2(i, 2, len) fac[i] = fac[i-1] * i % m;
  finv[len-1] = modpow(fac[len-1], m-2, m);
  for(int i = len-2; i >= 0; i--) finv[i] = finv[i+1] * (i+1) % m;
  return;
}

ll binom(ll n, ll k, ll m = MOD) {
  if(n < 0 || k < 0 || k > n) return 0;
  if(k < 100) {
    // n * ... * (n-k+1) / k!
    ll ans = 1;
    rep(i, k) ans *= (n - i), ans %= m;
    ans *= finv[k], ans %= m;
    return ans;
  }
  else {
    return fac[n] * finv[k] % m * finv[n-k] % m;
  }
}

// n mai ari, [1, a] wo tukau toki no sousuu
ll func(ll n, ll a, ll c) {
  return binom(n+c-1, a+c-1);
}

ll memofuncX[40][40];
ll memofuncY[40][40];

void solve() {
  ll X, Y, M, K; cin >> X >> Y >> M >> K;
  rep(a,40)rep(c,40){
    memofuncX[a][c]=func(X,a,c);
    memofuncY[a][c]=func(Y,a,c);
  }
  vector<array<ll, 2>> cards(K);
  rep(i, K) {
    ll a, b; cin >> a >> b;
    a--, b--;
    cards[i] = {min(a, b), max(a, b)};
  }
  sort(all(cards));
  cards.erase(unique(all(cards)), cards.end());
  vi deg(M,0);
  for(auto [a,b]:cards){
    deg[a]++;
    deg[b]++;
  }
  vi ID(M,0);
  int tmp=0;
  rep(i,M){
    if(deg[i]>0){
      ID[i]=tmp;
      tmp++;
    }
  }
  int free=M-tmp;
  M=tmp;

  ll must = 0;
  vector graph(M, vector<ll>());
  for(auto [a, b] : cards) {
    if(a == b) must |= (1<<ID[a]);
    else {
      graph[ID[a]].emplace_back(ID[b]);
      graph[ID[b]].emplace_back(ID[a]);
    }
  }

  vi NG(1<<M,0);
  vector<vector<pair<int,int>>>memo(1<<M,vector<pair<int,int>>(M,{-1,-1}));
  ll ans = 0;
  for(int bit=(1<<M)-1;bit>=0;bit--){
    
    ll p = __builtin_popcount(bit);
    rep(i,M){
      if(((bit>>i)&1)==0){
        NG[bit]|=NG[bit|(1<<i)];
      }
    }
    if(NG[bit])continue;
    if((bit&must)!=must)continue;
    if(bit!=(1<<M)-1){
      int add=-1;
      rep(i,M){
        if(((bit>>i)&1)==0)add=i;
      }
      vi flip(M,-1);
      int bit0=bit|(1<<add);
      memo[bit]=memo[bit0];
      for(auto v:graph[add]){
        auto [grp,col]=memo[bit0][v];
        if(grp==-1)continue;
        if(flip[grp]==-1){
          flip[grp]=1^col;
        }
        if(flip[grp]!=1^col){
          NG[bit]=1;
        }
      }
      memo[bit][add]={add,0};
      rep(i,M){
        auto [grp,col]=memo[bit][i];
        if(grp==-1)continue;
        if(flip[grp]!=-1){
          memo[bit][i]={add,col^flip[grp]};
        }
      }
    }
    if(NG[bit]==0){
      vi cnt0(M,0),cnt1(M,0);
      rep(i,M){
        auto [grp,col]=memo[bit][i];
        if(grp!=-1){
          if(col==0)cnt0[grp]++;
          else cnt1[grp]++;
        }
      }
      ll sm=0;
      vll dp(M+1);
      dp[0]=1;
      rep(i,M){
        if(cnt0[i]+cnt1[i]>0){
          vll ndp(M+1);
          rep(j,sm+1){
            ndp[j+cnt0[i]]+=dp[j];
            ndp[j+cnt1[i]]+=dp[j];
          }          
          sm+=cnt0[i]+cnt1[i];
          rep(j,M+1)dp[j]=ndp[j]%MOD;
        }
      }
      rep(c1,sm+1){
        int c2=sm-c1;
        ll val=dp[c1];
        ans += memofuncX[c1+p][free] * memofuncY[c2+p][free] % MOD * val % MOD;
        ans %= MOD;
        // print(c1, c2, val);
      }
    }
  }
  cout << ans << '\n';

  return;
}

int main() {
  precalc();
  ll T; cin >> T;
  while(T--) {
    solve();
  }

  return 0;
}

answer.code:16:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   16 | bool chmin(auto &a, auto b) {return a > b ? a = b, 1 : 0;}
      |            ^~~~
answer.code:16:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   16 | bool chmin(auto &a, auto b) {return a > b ? a = b, 1 : 0;}
      |                     ^~~~
answer.code:17:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   17 | bool chmax(auto &a, auto b) {return a < b ? a = b, 1 : 0;}
      |            ^~~~
answer.code:17:21: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   17 | bool chmax(auto &a, auto b) {return a < b ? a = b, 1 : 0;}
      |                     ^~~~
answer.code:33:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   33 | void print(auto x) {
      |            ^~~~
answer.code: In function ‘void solve()’:
answer.code:103:12: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  103 |   for(auto [a,b]:cards){
      |            ^
answer.code:119:10: error: missing template arguments before ‘graph’
  119 |   vector graph(M, vector<ll>());
      |          ^~~~~
answer.code:120:12: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  120 |   for(auto [a, b] : cards) {
      |            ^
answer.code:123:7: error: ‘graph’ was not declared in this scope; did you mean ‘isgraph’?
  123 |       graph[ID[a]].emplace_back(ID[b]);
      |       ^~~~~
      |       isgraph
answer.code:149:18: error: ‘graph’ was not declared in this scope; did you mean ‘isgraph’?
  149 |       for(auto v:graph[add]){
      |                  ^~~~~
      |                  isgraph
answer.code:150:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  150 |         auto [grp,col]=memo[bit0][v];
      |              ^
answer.code:161:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  161 |         auto [grp,col]=memo[bit][i];
      |              ^
answer.code:171:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  171 |         auto [grp,col]=memo[bit][i];
      |              ^