#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5,mod=1e9+7;
ll t,n,m,v,c[N],d[N],p,e[N];
ll ksm(ll n,ll k) {
	if(k==0) {
		return 1;
	} else if(k==1) {
		return n;
	} else if(k%2==0) {
		return ksm(n*n%mod,k/2);
	} else {
		return ksm(n*n%mod,k/2)*n%mod;
	}
}
int main() {
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	cin>>t;
	while(t--) {
		cin>>n>>m>>v;
		memset(e,0,sizeof(e)); 
		for(int i=1;i<=m;i++) {
			cin>>c[i]>>d[i];
		}
		if(n==m) {
			p=v*v;
			for(int i=1;i<n;i++) {
				if(e[d[i]]==0) {
					e[d[i]]=d[i+1];
					p-=v-1;
				} else if(e[d[i]]==-1) {
					continue;
				} else if(e[d[i]]!=d[i+1]) {
					e[d[i]]=-1;
					p--;
				}
			}
			cout<<ksm(p,n-1)<<'\n';
		}
	}
	return 0;
}

