#include<bits/stdc++.h>
#define LL long long
#define len(G) (LL)(G).size()
#define all(G) (G).begin(),(G).end()
#define ar(n) array<LL,n>
using namespace std;
using i128=__int128;
using ar=array<LL,2>;
using Poly=vector<LL>;

mt19937_64 rnd(random_device{}());

constexpr LL MOD=1e9+7;

Poly invfac;

template<class T>
inline void read(T &x)
{
	x=0;int w=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;	c=getchar();}
	while(isdigit(c)){x=x*10+(c^'0');	c=getchar();}
	if(w==-1)	x=-x;
}
template<class T,class... Args>
inline void read(T &x,Args &...args)
{
	read(x),read(args...);
}

LL d(LL S,LL i)
{
	return S>>i&1;
}
void dif(LL &S,LL i)
{
	if(d(S,i))	S^=1<<i;
}

LL norm(LL x,LL p=MOD)
{
	return (x%=p)<0?x+p:x;
}
LL add(LL a,LL b,LL p=MOD)
{
	return (a+=b)>=p?a-p:a;
}
LL inc(LL &a,LL b,LL p=MOD)
{
	return a=add(a,b,p);
}
LL sub(LL a,LL b,LL p=MOD)
{
	return (a-=b)<0?a+p:a;
}
LL dec(LL &a,LL b,LL p=MOD)
{
	return a=sub(a,b,p);
}
LL neg(LL x,LL p=MOD)
{
	return sub(0,x,p);
}
LL mul(LL a,LL b,LL p=MOD)
{
	return 1LL*a*b%p;
}
LL mult(LL &a,LL b,LL p=MOD)
{
	return a=mul(a,b,p);
}
LL qpow(LL a,LL b,LL p=MOD)
{
	LL x=a,ans=1;
	while(b)
	{
		if(b&1)	mult(ans,x,p);
		mult(x,x,p);
		b>>=1;
	}
	return ans%p;
}
LL inv(LL a,LL p=MOD)
{
	return qpow(a,p-2,p);
}
LL quo(LL a,LL b,LL p=MOD)
{
	return mul(a,inv(b,p),p);
}

LL fp(LL n,LL m)
{
	LL ans=1;
	for(LL i=n;i>n-m;--i)
		mult(ans,i);
	return ans;
}
LL C(LL n,LL m)
{
	return mul(fp(n,m),invfac[m]);
}
LL mC(LL n,LL m)
{
	if(n==0||m<0)	return 0;
	return C(n+m-1,n-1);
}

void solve()
{
	LL n1,n2,m,K;
	read(n1,n2,m,K);
	vector<ar> E(K);
	Poly N(m);
	LL H=0,G,nH;
	for(auto &[a,b]:E)
	{
		read(a,b);
		--a,--b;
		H|=1<<a|1<<b;

		N[a]|=1<<b;
		N[b]|=1<<a;
	}
	nH=__popcount(H);
	G=H;
	for(auto &[a,b]:E)
	{
		if(a==b)	dif(G,a);
	}
	Poly f(1<<m),g(1<<m);
	for(LL A=G;;A=(A-1)&G)
	{
		bool ok=1;
		for(LL i=0;i<m;++i)
		{
			if(d(A,i)&&(N[i]&A))
			{
				ok=0;
				break;
			}
		}
		if(!ok)	continue;

		LL nA=__popcount(A);
		f[A]=mC(m-nA,n2-nH+nA);
		g[A]=mC(m-nA,n1-nH+nA);

		if(!A)	break;
	}
	
	for(LL i=0;i<m;++i)
		for(LL S=0;S<(1<<m);++S)
			if(d(S,i))
				inc(g[S],g[S^(1<<i)]);

	LL ans=0;
	for(LL A=G;;A=(A-1)&G)
	{
		inc(ans,mul(f[A],g[G^A]));
		if(!A)	break;
	}
	printf("%lld\n",ans);
}

void init(LL n)
{
	invfac.resize(n+1);
	invfac[n]=inv(fp(n,n));
	for(LL i=n;i>=1;--i)
		invfac[i-1]=mul(invfac[i],i);
}

int main()
{
	init(20);

	LL T;
	read(T);
	while(T--)	solve();
	return 0;
}