//#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;
	ver[++len]=x;nex[len]=lin[y];lin[y]=len;
}
int now[1<<20];
int F[1<<20][21];
int Q[1<<20][41];
int S[1<<20][21];
int S1[1<<20][41];
int fa[1<<20][21];
int getfather(int v,int x)
{
	return x==fa[v][x]?x:fa[v][x]=getfather(v,fa[v][x]);
}
int getfather1(int v,int x)
{
	return x==Q[v][x]?x:Q[v][x]=getfather1(v,Q[v][x]);
}
void merge(int x,int y,int v)
{
	int xx=getfather(v,x);
	int yy=getfather(v,y);
	if(xx==yy)return;
	int s1=S[v][yy];
	int s2=S1[v][getfather1(v,y)];
	s1=s1-s2;
	if(s1<s2)swap(s1,s2);
	rep(0,m,j)
	{
		if(s1==s2)
		{
			g[j]=(ll)f[j+s1]*inv[2]%mod;
		}
		else
		{
			g[j]=f[j+s2];
			f[j+s1]=(f[j+s1]-g[j]+mod)%mod;
		}
	}
	rep(0,m,j)f[j]=g[j];
	S[v][xx]+=S[v][yy];
	fa[v][yy]=fa[v][xx];
}

void merge1(int v,int x,int y)
{
	int xx=getfather1(v,x);
	int yy=getfather1(v,y);
	if(xx==yy)return;
	Q[v][yy]=Q[v][xx];
	S1[v][xx]+=S1[v][yy];
}
void gx(int v,int x)
{
	int ww=0;
	Q[v][x]=x;Q[v][x+m]=x+m;
	S1[v][x]=1;
	fa[v][x]=x;
	S[v][x]=1;
	S1[v][x]=1;
	go(x)
	{
		if(Q[v][tn]==0)continue;
		int cc=getfather(v,tn);
		if(S[v][cc]==-1)
		{
			ww=1;break;
			continue;
		}
		merge(x,tn,v);
		merge1(v,x,tn+m);
		merge1(v,x+m,tn);
	}
	if(ww||getfather1(v,x)==getfather1(v,x+m))
	{
		S[v][x]=-1;now[v]=-2;return;
	}
	else
	{
		int s1=S[v][x];
		int s2=s1-S1[v][x];
		s1=s1-s2;
		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])%mod;
			if(j>=s2)f[j]=(f[j]+g[j-s2])%mod;
		}
	}
}
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;
		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,m,j)F[maxx][j]=0,fa[maxx][j]=0,S[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)S[i][j]=S[i^x][j],fa[i][j]=fa[i^x][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];
				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;
					ans=((ll)C(n1+res-1,g1+k+res-1)*C(n2+res-1,g1+gg-k+res-1)%mod*f[k]+ans)%mod;
				}
			}
			
		}
		put(ans);
	}
	return 0;
}