#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
int in(){
	int ans=0,f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) ans=ans*10+c-'0';
	return ans*f;
}
int n,m,T,v;
int x[1010],X[1010];
int a[1010],b[1010];
int ans;
int ch(){
	memcpy(X,x,sizeof(x));
	for(int i=1;i<n;i++){
		if(!x[i]) continue;
		if(x[i]==a[i]){
			if(x[i+1]!=0&&x[i+1]!=b[i]) return 0;
			x[i+1]=b[i];
		}
	}
	memcpy(x,X,sizeof(X));
	return 1;
}
void dfs(int p){
	if(p==n){
		if(ch()) ans++;
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[p]=i;b[p]=j;
			dfs(p+1);
		}
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	T=in();
	while(T--){
		n=in();m=in();v=in();
		if(n<=12){
			memset(x,0,sizeof(x));
			int fl=0;
			for(int i=1;i<=m;i++){
				int p=in();
				if(!x[p]) x[p]=in();
				else{
					int t=in();
					if(t!=x[p]) fl=1;
				}
			}
			if(fl){
				puts("0");
				continue;
			}
			ans=0;
			dfs(1);
			printf("%lld\n",ans%inf);
			continue;
		}
		else{
			int ans=1;
			for(int i=1;i<=m;i++){
				x[1]=in();x[2]=in();
			}
			for(int i=1;i<=n-1;i++) ans=(ans*v*v%inf);
			printf("%lld\n",ans);
		} 
	}
	
	return 0;
} 
