#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) {
  // ll res = 0;
  // for(ll b = 1; b <= a; ++b) {
  //   ll tmp = binom(a, b) * modpow(b, n) % MOD;
  //   if(a % 2 != b % 2) tmp *= -1;
  //   tmp = (tmp + MOD) % MOD;
  //   res += tmp;
  //   res %= MOD;
  // }
  // return res;
  return binom(n+c-1, a+c-1);
}

ll memoX[25][25],memoY[25][25];

void solve() {
  ll X, Y, M, K; cin >> X >> Y >> M >> K;
  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;
  rep(i,25)rep(j,25){
    memoX[i][j]=func(X,i,j);
    memoY[i][j]=func(Y,i,j);
  }

  for(int bit=(1<<M)-1;bit>=0;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];
        ll p = __builtin_popcount(bit);
        ans += memoX[c1+p][free] * memoY[c2+p][free]  % MOD * val % MOD;
        ans %= MOD;
        // print(c1, c2, val);
      }
    }
  }
  cout << ans << '\n';

  return;

  // search all subset
  ll res = 0;
  for(ll bit = 0; bit < (1<<M); ++bit) {
    if((bit & must) != must) continue;

    vector<ll> col(M, 0);
    rep(i, M) {
      if(bit & (1<<i)) col[i] = 3;
    }
    vector<array<ll, 2>> vec;
    queue<ll> que;
    bool ng = 0;
    rep(r, M) {
      if(col[r]) continue;
      ll r1 = 0, r2 = 0;
      col[r] = 1, r1++;
      que.push(r);
      while(que.size()) {
        ll v = que.front();
        que.pop();
        for(auto nv : graph[v]) {
          if(col[nv] == col[v]) {ng = 1; break;}
          if(col[nv]) continue;
          col[nv] = 3 - col[v];
          if(col[nv] == 1) r1++;
          else r2++;
        }
      }

      if(ng) break;
      vec.push_back({min(r1, r2), max(r1, r2)});
    }

    // cout << bitset<10>(bit) << endl;
    // for(auto [r1, r2] : vec) {
    //   cout << r1 << ' ' << r2 << endl;
    // }
    if(ng) continue;

    ll s = vec.size();
    vector<ll> dp(M+1, 0);
    dp[0] = 1;
    for(auto [a, b] : vec) {
      vector<ll> ndp(M+1, 0);
      rep(x, M+1) {
        if(x - a >= 0) ndp[x] += dp[x-a];
        if(x - b >= 0) ndp[x] += dp[x-b];
        ndp[x] %= MOD;
      }
      swap(dp, ndp);
    }

    ll p = __builtin_popcount(bit);
    rep(x, M+1) {
      ll s = x + p, t = M - x;
      // ll tmp = func(X, s) * func(Y, t) % MOD * dp[x] % MOD;
      res += tmp;
    }
    res %= MOD;

  }
  cout << res << endl;

  return;
}

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

  return 0;
}