#include <bits/stdc++.h>

using namespace std;

const int N = 21;
const int MSK = (1 << 20);
const int MOD = 1e9 + 7;

inline int add(int A, int B) {
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B) {
	if(A - B < 0) return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B) {
	return A * 1ll * B % MOD;
}

inline int pot(int A, int B) {
	int ret = 1;
	for(; B ; B >>= 1) {
		if(B & 1) ret = mul(ret, A);
		A = mul(A, A);
	}
	return ret;
}

int sus[N], n_1, n_2, m, k;
int dp[N][MSK], svi[MSK];

int ch[2][N], ob_ch[N][N];

void solve() {
	memset(sus, 0, sizeof(sus));
	scanf("%d%d%d%d", &n_1, &n_2, &m, &k); n_1--, n_2--;
	ch[0][0] = ch[1][0] = 1;
	for(int t = 1;t <= m;t++) {
		ch[0][t] = mul(ch[0][t - 1], mul(n_1 - t + 1, pot(t, MOD - 2)));
		ch[1][t] = mul(ch[1][t - 1], mul(n_2 - t + 1, pot(t, MOD - 2)));
	}
	
	int moraju = 0, vani = 0;
	for(int i = 0;i < k;i++) {
		int a, b; scanf("%d%d", &a, &b);
		a--, b--;
		vani |= (1 << a) | (1 << b);
		if(a == b) moraju |= 1 << a;
		else  {
			sus[a] |= (1 << b);
			sus[b] |= (1 << a);
		}
	}
	int Z = vani ^ moraju;

	vani = m - __builtin_popcount(vani);
	moraju = __builtin_popcount(moraju);

	int ind = 0;
	for(int msk = Z; msk; msk = (msk - 1) & Z) {
		svi[ind++] = msk;
	}
	dp[0][0] = 1;
	for(int i = ind - 1;i >= 0;i--) {
		int x = __lg(svi[i]);		
		int ss = (sus[x] & svi[i]) | (1 << x);
		int cnt = __builtin_popcount(svi[i]);
		int cnt2 = __builtin_popcount(ss) - 1;
		for(int j = 1;j <= cnt;j++)
			dp[j][svi[i]] = dp[j - 1][svi[i] ^ (1 << x)];
		for(int j = cnt2;j <= cnt;j++)
			dp[j][svi[i]] += dp[j - cnt2][svi[i] ^ ss];
	}
	int ans = 0;
	svi[ind] = 0;
	for(int i = 0;i <= ind;i++) {
		bool dobar = true;
		for(int j = 0;j < m;j++) {
			if((1 << j) & svi[i]) continue;
			if(!((1 << j) & Z)) continue;
			if(sus[j] & (Z ^ svi[i])) dobar = false;
		}
		if(!dobar) continue;
		int L = 0, R = 0;
		int vel = __builtin_popcount(svi[i]);
		for(int j = 0;j <= vel;j++) {
			for(int dod = 0;dod <= vani;dod++) {
				if(j + dod + (m - vani - vel) > 0)
					R = add(R, mul(ob_ch[vani][dod], mul(dp[j][svi[i]], ch[1][j + dod + (m - vani - vel) - 1])));
			}
		}
		for(int dod = 0;dod <= vani;dod++)
			if(vel + dod + moraju > 0)
				L = add(L, mul(ob_ch[vani][dod], ch[0][vel + dod + moraju - 1]));
		ans = add(ans, mul(L, R));
	}
	printf("%d\n", ans);
}

int main() {
	for(int i = 0;i < N;i++) ob_ch[i][i] = ob_ch[i][0] = 1;
	for(int n = 1;n < N;n++)
		for(int k = 1;k < n;k++)
			ob_ch[n][k] = add(ob_ch[n - 1][k - 1], ob_ch[n - 1][k]);
	int T; scanf("%d", &T);
	for(;T--;) solve();
	return 0;
}