#include<bits/stdc++.h>
using namespace std;
const int M=1e5+100;
const long long mod=1e9+7;
int T,n,m,v,c[M],d[M],ans;
long long t;
bool A;
int flag[1000000];
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m>>v;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&c[i],&d[i]);
		}
		ans=1;
		if(n==m){
			A=1;
			for(int i=1;i<=m;i++){
				if(c[i]!=i) A=0;
			}
			if(A){
				t=v*v-v+1;
				t%=mod;
				for(int i=1;i<=n-1;i++){
					ans=ans*t%mod;
				}
				cout<<ans<<"\n";
				continue;
			}
		}
		cout<<0<<endl;
	}
	
	return 0;
}
