#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=1e9+7;
long long t,n,m,v,ans,a[N],b[N],x[N],c[N],d[N];
bool dfs2(int p){
	if(p>n){
		for(int i=1;i<=m;++i)
			if(x[c[i]]!=d[i]) return 0;
		for(int i=1;i<n;++i)
			if(x[i]==a[i]&&x[i+1]!=b[i]) return 0;
		return 1;
	}
	for(int i=1;i<=v;++i){
		x[p]=i;
		if(dfs2(p+1)) return 1;
	}
	return 0;
}
void dfs(int p){
	if(p>=n){
		ans+=dfs2(1);
		return;
	}
	for(int j=1;j<=v;++j)
		for(int k=1;k<=v;++k) a[p]=j,b[p]=k,dfs(p+1);
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>m>>v;
		ans=1;
		for(int i=1;i<n;++i) ans=(ans*(v*v-v+1))%mod;
		for(int i=1;i<=m;++i) cin>>c[i]>>d[i];
		if(n<=10) ans=0,dfs(1);
		cout<<ans<<endl;
	}
	return 0;
}
