#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,v,c[100005],d[100005],a[100005],aa[100005],bb[100005],ans,s[20];
const int mod=1e9+7;
int ksm(int x,int y){
	int b=1;
	for(;y;y>>=1,x=x*x%mod)if(y&1)b=b*x%mod;
	return b;
}
void dfs(int x){
	if(x>=n){
		for(int i=1;i<=n;i++)s[i]=a[i];
		for(int i=1;i<n;i++){
			if(s[i]==aa[i]){
				if(s[i+1]&&s[i+1]!=bb[i])return;
				if(!s[i+1])s[i+1]=bb[i];
			}
		}
		ans++;
		return;
	}
	for(int i=1;i<=v;i++){
		aa[x]=i;
		for(int j=1;j<=v;j++){
			bb[x]=j;
			dfs(x+1);
			bb[x]=0;
		}
		aa[x]=0;
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n>>m>>v;
		if(m==1){
			for(int i=1;i<=m;i++)cin>>c[i]>>d[i];
			cout<<ksm(v*v%mod,n-1)<<endl;
		}else{
			for(int i=1;i<=n;i++)a[i]=0;
			bool flag=1;
			for(int i=1;i<=m;i++){
				cin>>c[i]>>d[i];
				if(a[c[i]]!=0&&a[c[i]]!=d[i])flag=0;
				a[c[i]]=d[i];
			}
			if(!flag){
				cout<<0<<endl;
				continue;
			}
			ans=0;
			dfs(1);
			cout<<ans<<endl;
		}
	}
	return 0;
}
