#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+5,mod=1e9+7;
int n,m,v,ans,a[N],p[N],q[N];
bool check(){
	vector<bool>u(N,false);
	for (int i=1;i<n;i++){
		if (a[i]==p[i]){
			if (a[i+1]!=0&&a[i+1]!=q[i])  return 0;
			else if (a[i+1]==0) a[i+1]=q[i],u[i+1]=1;
		}
	}
	for (int i=1;i<=n;i++)
		if (u[i])  u[i]=0,a[i]=0;
	return 1;
}
void dfs(int k){
	if (k==n){
		if (check())  ans=(ans+1)%mod;
		return;
	}
	for (int i=1;i<=v;i++)
		for (int j=1;j<=v;j++){
			p[k]=i,q[k]=j;
			dfs(k+1);
		}
	return;
}
void work(){
	memset(a,0,sizeof(a));
	ans=0;
	scanf("%d %d %d",&n,&m,&v);
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		if (a[x]!=0)  {printf("0\n");return;}
		a[x]=y;
	}
/*	if (n==m){
		ull tn=n,tv=v;
		printf("%llu\n",((tn-1)*((tv-1)*tv+1)%mod)%mod);
		return;
	}*/
	dfs(1);
	printf("%d\n",ans);
	return;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int t;
	scanf("%d",&t);
	while (t--)  work();
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2

*/
