#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int mod=1e9+7;
int T,n,m,v;
int vis[10005];
struct node {
	int c,d;
} q[N];
int qm(int x,int k) {
	if(k==0)return 1;
	int mi=x,tp=1;
	while(k>=2) {
		if(k%2) {
			tp*=x;
			tp%=mod;
			k--;
		}
		x=x*x;
		x%=mod;
		k/=2;
	}
	return x*tp%mod;
}
map<int,int>mp;
signed main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%d",&T);
	while(T--) {
		mp.clear();
		bool flaga=0;
		memset(q,0,sizeof q);
//		memset(vis,0,sizeof vis);
//		memset(tt,0,sizeof tt);
		scanf("%lld%lld%lld",&n,&m,&v);
		if(n==m)flaga=1;
		for(int i=1; i<=m; i++) {
			int c,d;
			scanf("%lld%lld",&c,&d);
			mp[c]++;
			if(c!=i)flaga=0;
		}
//		if(flaga) {
		long long res=qm((v-1)*v+1,n-1);
		printf("%lld\n",res%mod);
		continue;
//		}

	}
	return 0;
}
/*
3
2 1 2
1 1
2 2 2
1 1
2 2
2 2 2
1 1
1 2
*/
