#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int T,n,m,v;
const int mod=1e9+7;
int f[100010][3];
signed 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++){
			int c,d;
			cin>>c>>d;
		}
		f[n][0]=f[n][1]=1;
		if(m==1){
			int ans=1;
			int u=n-1;
			while(u!=0){
				ans=(ans*v)%mod;
				u--;
			}
			u=n-1;
			while(u!=0){
				ans=(ans*v)%mod;
				u--;
			}
			cout<<ans<<endl;
		}
		else if(n==m){
			for(int i=n-1;i>=1;i--){
				f[i][1]=(f[i+1][1]+f[i+1][0])%mod;
				f[i][0]=(v-1)*(f[i+1][0]+f[i+1][1])%mod;
			}
			cout<<(f[1][1]+f[1][0])%mod<<endl;
		}
	}
	return 0;
}
/*
1
2 2 2
1 1 
2 2

*/
