//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#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;
}
set<int> s[22];
int now[1<<20];
int F[1<<20][21];
int Q[1<<20][41];
int S1[1<<20][41];
int c1[22],c2[22];
int getfather1(int v,int x)
{
	return x==Q[v][x]?x:Q[v][x]=getfather1(v,Q[v][x]);
}
void merge1(int v,int x,int y)
{
	int xx=getfather1(v,x);
	int yy=getfather1(v,y);
	if(xx==yy)return;
	if(yy<=m)
	{
		int s1=S1[v][yy];
		int s2=S1[v][yy+m];
		if(s1<s2)swap(s1,s2);
		rep(0,m,j)
		{
			if(s1==s2)
			{
				g[j]=f[j]/2;
			}
			else
			{
				g[j]=f[j+s2];
				f[j+s1]=f[j+s1]-g[j];
			}
		}
		rep(0,m,j)f[j]=g[j];
	}
	Q[v][yy]=Q[v][xx];
	S1[v][xx]+=S1[v][yy];
}
void gx(int v,int x)
{
	Q[v][x]=x;Q[v][x+m]=x+m;
	S1[v][x]=1;
	go(x)
	{
		if(Q[v][tn]==0)continue;
		merge1(v,x,tn+m);
		merge1(v,x+m,tn);
	}
	if(getfather1(v,x)==getfather1(v,x+m))
	{
		now[v]=-2;return;
	}
	else
	{
		int s1=S1[v][x];
		int s2=S1[v][x+m];
		rep(0,m,j)g[j]=f[j],f[j]=0;
		fep(m,0,j)
		{
			if(j>=s1)f[j]=(f[j]+g[j-s1]);
			if(j>=s2)f[j]=(f[j]+g[j-s2]);
		}
	}
}
int main()
{
	//freopen("1.in","r",stdin);
	sc(T);
	prepare();
	rep(1,T,TT)
	{
		sc(n1);sc(n2);sc(m);sc(k);

		rep(1,m,i)lin[i]=vis[i]=0,s[i].clear();
		len=ww=gd=0;
		rep(1,k,i)
		{
			int x,y;
			sc(x);sc(y);
			s[x].insert(y);
			s[y].insert(x);
			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;

		rep(0,m,j)c1[j]=C(n1+res-1,j),c2[j]=C(n2+res-1,j);

		int cc=0;
		rep(1,m,i)if(vis[i]==1)
		{
			++cc,w[1<<(cc-1)]=i;
			for(auto x:s[i])
			{
				if(x==i)continue;
				if(vis[x]!=1)continue;
				add(i,x);
			}
		}
		int maxx=1<<cnt;--maxx;
		int ans=0;
		
		rep(0,m,j)F[maxx][j]=0,f[j]=0;
		rep(1,m*2,j)Q[maxx][j]=0,S1[maxx][j]=0;
		F[maxx][0]=1;
		now[maxx]=-1;
		f[0]=1;
		fep(maxx,0,i)
		{
			
			if(i!=maxx)
			{
				int ww=i^maxx;
				int x=ww&(-ww);
				int id=w[x];
				rep(0,m,j)f[j]=F[i^x][j];
				rep(1,m*2,j)Q[i][j]=Q[i^x][j],S1[i][j]=S1[i^x][j];
				now[i]=now[i^x];
				if(now[i]!=-2)gx(i,id);
			}
			if(now[i]!=-2)
			{
				++now[i];
				int gg=now[i];
				int g1=gd+cnt-now[i];
				rep(0,m,k)
				{
					F[i][k]=f[k];
					if(!f[k])continue;
					if(g1+k+res-1<0)continue;
					if(g1+gg-k+res-1<0)continue;
					ans=((ll)c1[g1+k+res-1]*c2[g1+gg-k+res-1]%mod*f[k]+ans)%mod;
				}
			}
		}
		put(ans);
	}
	return 0;
}