#include<bits/stdc++.h>
#define sc scanf
#define pr printf
#define mst(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=1e9+7;
int T;
ll n,m,v,a[N],jc[N],inv[N];
ll ksm(ll x,ll y){
	ll z=1;
	while(y){
		if(y&1) z=z*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return z;
}
//void init(){
//	ll i;
//	jc[0]=1;
//	for(i=1;i<=N;i++){
//		jc[i]=(jc[i-1]*i)%mod;
//	}
//	inv[1]=1;
//	for(i=2;i<=N;i++){
//		inv[i]=((mod-mod/i)*inv[mod%i])%mod;
//	}
//}
//ll C(ll x,ll y){
//	return jc[x]*inv[jc[y]*jc[x-y]%mod]%mod;
//}
void solve(){
	int i;
	ll x,y;
	sc("%lld%lld%lld",&n,&m,&v);
//	cout<<n<<" "<<m<<" "<<v<<" "<<T<<endl;
	if(m==1){
		sc("%lld%lld\n",&x,&y);
		pr("%lld\n",ksm(v*v%mod,n-1));
		return ;
	}
//	else pr("0\n");
	for(i=1;i<=m;i++){
		sc("%lld%lld",&x,&y);
		x=y;
	}
	pr("0\n");
//	if(n<=12&&m<=12&&v<=2){
//		for(i=1;i<=v;i++){
//			for(j=1;j<=v;j++){
//				
//			}
//		}
//	}	
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	sc("%d",&T);
//	init();
	while(T--){
		solve();
	}
	return 0;
}
