#include<cstdio>
using namespace std;
int c[100005],d[100005];
int main()
{
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	//freopen(zhapian); 
	int t;
	bool pd1=1,pd2=1;
	scanf("%d",&t);
	while(t--){
		int n,m,v;
		scanf("%d %d %d",&n,&m,&v);
		if(n!=m)pd1=0;
		for(int i=1;i<=m;i++){
			scanf("%d %d",&c[i],&d[i]);
			if(c[i]!=i)pd1=0;
		}
		if(pd1){
			long long ans=n-1;
			long long cnt=v;
			cnt*=(v-1);
			cnt%=1000000007;
			cnt++;
			ans*=cnt;
			ans%=1000000007;
			printf("%lld\n",ans);
		}
	}
	return 0;
}
