#include<bits/stdc++.h>
#define int long long
#define _ 500005
#define mod 1000000007
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
inline int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res%mod;
}
int t,n,m,v,flag,a[_],p[_],c[_],d[_],tot;
struct node{int a,b;}x[_];
void dfs(int now){
	if(now==n){
		for(int i=1;i<=n;i++)p[i]=a[i];
		for(int i=1;i<n;i++){
			if(p[i]==x[i].a){
				if(p[i+1]!=-1&&p[i+1]!=x[i].b)return;
				p[i+1]=x[i].b;
			}
		}
		++tot;return;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			x[now].a=i,x[now].b=j;
			dfs(now+1);
		}
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	t=read();
	while(t--){
		n=read(),m=read(),v=read(),tot=0,flag=0;
		for(int i=1;i<=n;i++)a[i]=-1,x[i].a=-1,x[i].b=-1;
		for(int i=1;i<=m;i++){
			c[i]=read(),d[i]=read();
			if(c[i]<=100000){
				if(a[c[i]]!=-1&&d[i]!=a[c[i]])flag=1,a[c[i]]=d[i];
				a[c[i]]=d[i];	
			}
		}
		if(flag){puts("0");continue;}
		if(n<=12){
			dfs(1);
			printf("%lld\n",tot);
		}else if(m==1){
			int ans=1;
			printf("%lld\n",qpow(v,2*n-2));
		}else{
			int ans=1;
			for(int i=1;i<n;i++)ans=(ans*(1+(v*(v-1)%mod)))%mod;
			printf("%lld\n",ans);
		}
	}
	return 0;
}
