#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int T,n,m,cnt,num[N],ncnt,aa[N],bb[N];
long long v,ans;
bool flag1,flag2;
map<int,int>ma;
struct ask{
	int c,d;
}a[N];
bool cmp(ask a,ask b){
	if(a.c==b.c) return a.d<b.d;
	return a.c<b.c;
}
long long ksm(long long a,int b){
	long long res=1;
	while(b){
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
bool check(){
	int now=0;
	for(int i=1;i<=n;i++){
		if(now){
			if(ma[i]&&now!=ma[i]) return 0; 
			if(now==aa[i]) now=bb[i];
			else now=0;
		}
		else if(ma[i]==aa[i]) now=bb[i];
	}
	return 1;
}
void dfs(int i){
	if(i==n) {
		ans+=check();
		return;
	}
	for(int j=1;j<=v;j++){
		for(int k=1;k<=v;k++){
			aa[i]=j,bb[i]=k;
			dfs(i+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		ma.clear();
		scanf("%d%d%lld",&n,&m,&v);
		long long v2=(v*v)%mod;
		flag1=0;
		flag2=(n==m);
		cnt=m;
		ncnt=0;
		ans=ksm(v2,n-1);
		for(int i=1;i<=m;i++) {
			scanf("%d%d",&a[i].c,&a[i].d);
			if(a[i].c!=i) flag2=0;
			if(ma[a[i].c]&&ma[a[i].c]!=a[i].d) flag1=1;
			if(!ma[a[i].c]) num[++ncnt]=a[i].c;
			ma[a[i].c]=a[i].d;
		}
		if(flag1){
			printf("0\n");
			continue;
		}
		if(flag2){
			long long a=((long long)(v-1)*v+1)%mod;
			ans=ksm(a,n-1);
			printf("%lld\n",ans%mod);
			continue;
		}
		sort(num+1,num+1+ncnt);
		if(ncnt==1) {
			printf("%lld\n",ans);
			continue;
		}
		if(v==2){
			memset(aa,0,sizeof(aa));
			memset(bb,0,sizeof(bb));
			dfs(1);
			printf("%lld\n",ans);
			continue;
		}
		printf("0\n");
	}
	return 0;
}

