#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const int N=1e6+5;
LL t,n,m,v;
int c[N],d[N];
int an[N];
LL qkpow(LL x,LL y){
	x%=MOD;
	LL res=1;
	while(y){
		if(y&1)res=res*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return res;
}
LL dp[N],jc[N];
int pos,ap[N],tst[N];
int a[N],b[N],ans;
void dfs(int x){
	if(x>=n){
		for(int i=1;i<=n;i++)
			tst[i]=an[i];
		for(int i=1;i<n;i++){
			if(tst[i]==a[i]){
				if(tst[i+1]>0&&tst[i+1]!=b[i])return ;
				tst[i+1]=b[i];
			}
		}
		ans++;
		return ;
	}
	for(int i=1;i<=v;i++){
		for(int j=1;j<=v;j++){
			a[x]=i,b[x]=j;
			dfs(x+1);
		}
	}
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&v);
		pos=0;
		bool tp=1;
		for(int i=1;i<=n;i++)
			dp[i]=0,jc[i]=0,an[i]=0,ap[i]=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&c[i],&d[i]);
			if(c[i]!=i)tp=0;
			an[c[i]]=d[i];
		}
		bool tf=1;
		for(int i=1;i<=m;i++){
			if(an[c[i]]!=d[i]){
				tf=0;break;
			}
		}
		if(!tf){printf("0\n");continue;}
		if(m==1){printf("%lld\n",qkpow(v,2*(n-1)));continue;}
		if(m==n&&tp){
			LL rs=qkpow((v*v%MOD-(v-1)+MOD)%MOD,(n-1));
			printf("%lld\n",rs);
			continue;
		}
		dfs(1);
		printf("%d\n",ans);
	}
	return 0;
}
