#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;
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;
  }
}

ll func(ll n, ll a) {
  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;
}

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

  // 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() {
  ll T; cin >> T;
  while(T--) {
    solve();
  }

  return 0;
}