#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10 , mod = 1e9 + 7;

int c[N],d[N],n,m,v,x[N],q[N],b[N],ans;
int a[N];
bool vis[N];
bool chk(){
	for(int i=1;i<n;i++){
		if(x[i]==a[i]&&x[i+1]&&x[i+1]!=b[i])  return false;
	}
	return true;
}
void dfs(int k){
	if(k==n){
//		for(int i=1;i<n;i++)  cout<<a[i]<<" ";cout<<endl;
//		for(int i=1;i<n;i++)  cout<<b[i]<<" ";cout<<endl;
		if(chk())  ans++;
		if(ans>mod)  ans-=mod;
		return;
	}
	for(int i=1;i<=v;i++){
		a[k]=i;
		for(int j=1;j<=v;j++){
			b[k]=j;
			dfs(k+1);
		}
	}
}
void solve(){
	memset(x,0,sizeof x);memset(vis,false,sizeof vis);
	cin>>n>>m>>v;ans=0;bool fs=true;
	for(int i=1;i<=m;i++){
		cin>>c[i]>>d[i];
		if(vis[c[i]]&&x[c[i]]!=d[i]){
			fs=false;
		}
		vis[c[i]]=true;
		x[c[i]]=d[i];
	}  
	if(!fs){
		cout<<0<<endl;
		return;
	}
	dfs(1);
	cout<<ans<<endl;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int T;cin>>T;
	while(T--)  solve();
	return 0;
}
