#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,mod=1e9+7;
int n,m,v;
int a[N],b[N],c[N],d[N];
struct node{
	int pos,val;
}t[N];
int sum,cnt,xq;
int ans5;
map<int,int>MP;
int check(){
	int now=0;
	for(int i=1;i<n;i++){
		if(a[i]==MP[i])now=1;
		else if(a[i]!=b[i-1])now=0;
		if(now&&b[i]!=MP[i+1]&&MP[i+1])return 0;
	}
	return 1;
}
void dfs5(int x){
	if(x==n){
		if(check())ans5++;
		return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[x]=i;
			b[x]=j;
			dfs5(x+1);
		}
	}
}
void solve5(){
	ans5=0;
	dfs5(1);
	printf("%d\n",ans5);
}
int qpow(int a,int b){
	int ans=1;
	for(int x=a,j=b;j;j>>=1,x=x*x%mod){
		if(j&1)ans=ans*x%mod;
	}
	return ans;
}
bool cmp(node x,node y){
	return x.pos<y.pos;
}
void solve(){
	MP.clear();
	cnt=0;
	scanf("%d%d%d",&n,&m,&v);
	sum=qpow(v,2*n-2),xq=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&c[i],&d[i]);
	}
	for(int i=1;i<=m;i++){
		if(MP[c[i]]){
			if(MP[c[i]]==d[i])continue;
			else {
				puts("0");
				return;
			}
		}
		MP[c[i]]=d[i];
		t[++cnt].pos=c[i];
		t[cnt].val=d[i];
	}
	if(n+m<=30){
		solve5();
		return;
	}
	printf("%d\n",sum);
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	int testcase;
	scanf("%d",&testcase);
	while(testcase--){
		solve();
	}
	return 0;
} 
