#include<iostream>
#define ll long long
using std::cin;
using std::cout;
const ll N=1,p=1e9+7;
ll pow(ll x,ll y){
	ll ans=1;
	while(y){
		if(y&1)
			(ans*=x)%=p;
        y>>=1,(x*=x)%=p;
	}
    return ans;
}
int main(){
    freopen("assign.in","r",stdin);
    freopen("assign.out","w",stdout);
    std::ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ll T,n,m,v,i,j,k,ans;
    cin>>T;
    while(T--){
        cin>>n>>m>>v;
        for(i=1;i<=m;++i)
            cin>>j>>k;
        if(m==1){
            cout<<pow(v*v%p,n-1)<<'\n';
        }
        else{
            ans=pow(v*v%p,n-1);
            for(i=n-1;i>1;--i)
                (ans-=(v-1)*(v-1)%p*v%p*pow(v*v%p,i-2)%p)%=p;
            (ans-=(v-1))%=p;
            cout<<(ans+p)%p<<'\n';
        }
    }
    
    return 0; 
}
