#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int t,x[1000006],c[1000006],d[1000006],n,m,v; 
int quick(int a,int b){
	int c=0,d=b,e=a;
	while(d){
		if(d%2)c=(c+e)%mod;
		d/=2;
		e=(e*e)%mod;
	}
	return c;
}
void deal(){
	cin>>n>>m>>v;
	for(int i=1;i<=m;i++){
		cin>>c[i]>>d[i];
	}
	if(m==1){
		cout<<quick(v,(n-1)*2)<<"\n"; 
		return ;
	}
	else if(m==n){
		int ans=1;
		for(int i=1;i<n;i++)ans=ans%mod*((v*(v-1))%mod+1)%mod,ans%=mod;
		cout<<ans<<"\n";
	}
}
signed main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--){
		deal();
	}
	return 0;
}
