#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define cmx(x,y) x = max(x,y)
#define cmn(x,y) x = min(x,y)
#define ary(k) array<int,k>
typedef pair<int,int> pii;
typedef vector<int> vi;
const int MOD = 1e9+7;
void solve(){
	int n,m,k; cin >> n >> m >> k;	
	vector<vi> adj(n);
	rep(i,0,m){
		int u,v; cin >> u >> v;
		u--; v--;
		adj[u].PB(v); adj[v].PB(u);
	}
	vector<vi> dp(n+1,vi(2));
	dp[1][0] = k; dp[1][1] = 0;
	rep(i,2,n+1){
		dp[i][0] = dp[i-1][1];
		dp[i][1] = ((k-1)*dp[i-1][0]%MOD+(k-2)*dp[i-1][1]%MOD);
	}
	auto fpow = [&](int x, int y){
		int z = 1; for(; y; y /= 2, x = x*x%MOD) if(y & 1) z = z*x%MOD;
		return z;
	};
	int rat = (k-1)*fpow(k,MOD-2)%MOD;
	vi vis(n),stk,cyc(n,-1),cnt(n); int id = 0;
	auto dfs = [&](auto& dfs, int u, int p)->void{
		vis[u] = 1; stk.PB(u);
		for(int v : adj[u]) if(v != p){
			if(!vis[v]) dfs(dfs,v,u);
			else if(vis[v] == 1){
				for(int i = sz(stk)-1; i >= 0; i--){
					cyc[stk[i]] = id;
					//cout << id << " " << stk[i] << "\n";
					cnt[id]++;
					if(stk[i] == v) break;
				}
				id++;
			}
		}
		vis[u] = 2; stk.pop_back();
	};
	dfs(dfs,0,-1);
	rep(i,0,n)if(cyc[i] == -1){
		cnt[i] = 1;
		cyc[i] = id++;
	}
	vector<vi> g(id);
	rep(u,0,n) for(int v : adj[u]) if(cyc[u] != cyc[v]){
		//cout << cyc[u] << " " << cyc[v] << "\n";
		g[cyc[u]].PB(cyc[v]);
	}
	auto dfs1 = [&](auto& dfs1, int u, int p)->int{
		int cur = (cnt[u] == 1 ? k : dp[cnt[u]][1]);
		for(int v : g[u]) if(v != p){
			int nxt = dfs1(dfs1,v,u);
			cur = cur*nxt%MOD*rat%MOD;
		}
		//cout << u << " " << cur << "\n";
		return cur;
	};
	int ans = dfs1(dfs1,0,-1);
	cout << ans << "\n";
}
signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	int t; cin >> t; while(t--) solve();
}