#include<bits/stdc++.h>
#define ll long long
#define db double
#define INF 1100000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x)
#define putl_(x) printf("%lld ",x)
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;i+=1)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ui unsigned
#define sq sqrt
#define l(w) t[w].l
#define r(w) t[w].r
#define x(w) t[w].x
#define tag(w) t[w].tag
#define sum(w) t[w].sum
#define sc(A) scanf("%d",&A)
#define scl(A) scanf("%lld",&A)
#define scs(A) scanf("%s",A);
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
#define uint unsigned int
#define mod 1000000007
#define zz p<<1
using namespace std;
const int MAXN=410;

int T,n1,n2,m,k,id;
int vis[MAXN];

int cnt,gd,ww,len,flag,res;


int w[1<<21],col[MAXN],sum[MAXN];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1];
int q[MAXN][2],l;
int fac[MAXN],inv[MAXN],dfn[MAXN];
int f[MAXN],g[MAXN];
int ksm(int b,int p)
{
	int cnt=1;
	while(p)
	{
		if(p&1)cnt=(ll)cnt*b%mod;
		b=(ll)b*b%mod;p=p>>1;
	}
	return cnt;
}
void prepare()
{
	int ww=100;
	fac[0]=1;
	rep(1,ww,i)fac[i]=(ll)fac[i-1]*i%mod;
	inv[ww]=ksm(fac[ww],mod-2);
	fep(ww-1,0,i)inv[i]=(ll)inv[i+1]*(i+1)%mod;
}
int C(int a,int b)
{
	int cc=1;
	fep(a,a-b+1,i)cc=(ll)cc*i%mod;
	return (ll)cc*inv[b]%mod;
}
void add(int x,int y)
{
	ver[++len]=y;nex[len]=lin[x];lin[x]=len;
	ver[++len]=x;nex[len]=lin[y];lin[y]=len;
}
void dfs(int x,int cc)
{
	dfn[x]=id;col[x]=cc;++sum[cc];
	go(x)
	{
		if(vis[tn]!=1)continue;
		if(dfn[tn]==id){if(col[x]==col[tn])flag=1;}
		else dfs(tn,cc^1);
	}
}
int main()
{
	sc(T);
	prepare();
	rep(1,T,TT)
	{
		sc(n1);sc(n2);sc(m);sc(k);
		rep(1,m,i)lin[i]=vis[i]=0;
		len=ww=gd=0;
		rep(1,k,i)
		{
			int x,y;
			sc(x);sc(y);
			if(x!=y)add(x,y);
			if(x==y&&vis[x]!=2)++gd,vis[x]=2;
			if(!vis[x])vis[x]=1;
			if(!vis[y])vis[y]=1;
		}
		rep(1,m,i)if(vis[i])++ww;
		cnt=ww-gd;res=m-ww;
		int cc=0;
		rep(1,m,i)if(vis[i]==1)++cc,w[1<<(cc-1)]=i;
		int maxx=1<<cnt;--maxx;
		int ans=0;
		rep(0,maxx,i)
		{
			int j=i;
			while(j)
			{
				int x=j&(-j);
				vis[w[x]]=2;
				j-=x;++gd;
			}
			++id;l=0;int gg=0;flag=0;
			rep(1,m,k)if(dfn[k]!=id&&vis[k]==1)
			{
				dfs(k,0);
				++l;
				q[l][0]=sum[0];
				q[l][1]=sum[1];
				gg+=sum[0]+sum[1];
				sum[0]=sum[1]=0;
			}
			//cout<<l<<' '<<i<<' '<<gg<<endl;
			//rep(1,m,i)cout<<vis[i]<<' ';
			//cout<<endl;
			if(!flag)
			{
				f[0]=1;
				int lim=0;
				rep(1,l,k)
				{
					lim+=max(q[k][0],q[k][1]);
					rep(0,lim,j)g[j]=f[j],f[j]=0;
					fep(lim,0,j)
					{
						if(j>=q[k][0])f[j]+=g[j-q[k][0]];
						if(j>=q[k][1])f[j]+=g[j-q[k][1]];
					}
					
				}
				int cnt=0;
				rep(0,lim,k)
				{
					if(!f[k])continue;
					ans=((ll)C(n1+res-1,gd+k+res-1)*C(n2+res-1,gd+gg-k+res-1)%mod*f[k]+ans)%mod;
					cnt=(cnt+(ll)C(n1+res-1,gd+k+res-1)*C(n2+res-1,gd+gg-k+res-1)%mod*f[k])%mod;
					//cout<<k<<' '<<f[k]<<' '<<C(n1+res-1,gd+k+res-1)<<' '<<n1+res-1<<' '<<gd+k+res-1<<' '
					//<<res<<' '<<C(n2+res-1,gd+gg-k+res-1)<<endl;
					f[k]=0;
				}
				//rep(0,lim,k)cout<<f[k]<<endl;
				//cout<<i<<' '<<cnt<<endl;
			}
			j=i;
			while(j)
			{
				int x=j&(-j);
				vis[w[x]]=1;
				j-=x;--gd;
			}
		}
		put(ans);
	}
	return 0;
}