#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(register int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int MAXN = (int)1e5+10;
const int INF = 0x3f3f3f3f;
const int mod = (int)1e9+7;
inline ll read(){
	register ll x=0,f=1;char c = getchar();
	while(!isdigit(c)){if(c=='-')f=0;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
template<typename T>
inline void write(T x){
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
ll T,n,m,v,c[MAXN],d[MAXN],x[MAXN],ans,flag;
ll quickpow(ll x,ll k){
	ll res = 1;
	while(k){
		//cout<<1;
		if(k&1) res = (res*x)%mod;
		x = (x*x)%mod;
		k >>= 1;
	}
	return res%mod;
}
int main(){
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);
	T = read();
	while(T--){
		flag = 0;
		memset(x,0,sizeof(x));
		n = read();m = read();v = read();
		FOR(i,0,m){
			c[i] = read();
			d[i] = read();
		}
		ans = 1;
		if(flag) ans = 0;
		else if(m==1){//6,7,8,9
			ans = quickpow((v*v)%mod,n-1);
		}else{
			FOR(i,1,n){
				if(x[i]&&x[i+1]) ans = (ans*(((v-1)*v+1)%mod))%mod;
				else ans = (ans*((v*v)%mod))%mod;
			}//ÐÔÖÊB 
		}
		write(ans%mod);
		putchar('\n');
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
 
