#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1e5+50,MOD=1e9+7;
ll t,ans,an[N];

int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		ll n,m,v;
		ans=0;
		scanf("%lld%lld%lld",&n,&m,&v);
		while(m--){
			ll x,y;
			scanf("%lld%lld",&x,&y);
		}
		ans=1;
		an[0]=1;
		for(ll i=1;i<=n;i++){
			an[i]=an[i-1]*(v-1),an[i]%=MOD;
			ans+=an[i],ans%=MOD;
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}
