#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <time.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// to erase in multiset-> less_equal<T> and 
// s.erase(s.find_by_order(s.order_of_key(x)))
// lower_bound(x)=>(cannot use the stl lower_bound function)
// ll idx = s.order_of_key(x)
// if(idx == s.size()) -> no lower_bound
// else lb = *s.find_by_order(idx) // as 0-indexing
// idx-1 will give highest value which is strictly less than x
// for upper_bound->do the same with (x+1)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef tuple<ll, ll, ll> t64;
typedef vector<t64> vt64;
typedef vector<vt64> vvt64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<vector<p32> > vvp32;
typedef vector<bool> vb;
ll mod =  1e9+7, MOD = 998244353;
double eps = 1e-12;
// #define forn(i,e) for(ll i = 0; i < e; i++)
#define FOR(s, e, i) for(int i = s; i <= e; i++)
// #define rforn(i,s) for(ll i = s; i >= 0; i--)
#define ROF(s ,e, i) for(int i = s; i >= e; i--)
#define coutAll(A) for(auto asdafas : A) cout <<  asdafas << " "; cout << "\n";
#define foutAll(A) for(auto asdafas : A) fout <<  asdafas << " "; cout << "\n";
#define cinAll(A) for(auto &asdafas : A) cin >>  asdafas;
#define finAll(A) for(auto &asdafas : A) fin >>  asdafas;
#define minpq priority_queue<ll, v64, greater<ll>>
#define maxpq priority_queue<ll> 
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
ll inf = LLONG_MAX;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
//#define MAXN 1000000

ll powMod(ll x, ll y){
    ll res = 1;
    x %= mod;
    while(y > 0){
        if(y&1) (res *= x) %= mod;
        y >>= 1;
        (x *= x) %= mod;
    }
    return res;
}
void solve(int it)
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vv32 adj(n);
    FOR(0, m - 1, i){
        int u,v;
        scanf("%d%d", &u, &v);
        --u; --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vb oncycle(n, false);
    vb vis(n, false);
    v32 par(n, -1);
    int cycle = 0;
    v32 cyclesize;
    // cout << "done\n";
    auto dfs = [&](auto && self, ll u, ll p = -1)->void{
        // cout << u << " ";
        vis[u] = true;
        par[u] = p;
        for(auto v : adj[u]){            
            if(!vis[v]){
                self(self, v, u);
                continue;
            }
            int x = 0;
            if(par[u] != v){
                if(oncycle[v]) continue;
            // cout << "\nu = " << u <<  " v = " << v << "\n";
                ++cycle;
                int cur = u;
                while(cur != v){
                    // cout << cur << ", ";
                    ++x;
                    oncycle[cur] = true;
                    cur = par[cur];
                }
                oncycle[cur] = true;
                ++x;
                cyclesize.pb(x);
            }
        }
    };
    dfs(dfs, 0);
    // cout<< "done\n";
    // if(cycle == 0){
    //     ll ans = k;
    //     FOR(1, n-1, i) (ans *= k-1) %= mod;
    //     cout << ans << "\n";
    //     return;
    // }
    ll ans = 1;
    bool ok = true;
    FOR(0, n - 1, i){
        if(!oncycle[i]){
            if(ok){
                (ans *= k) %= mod;
                ok = false;
            }else{
                (ans *= k - 1) %= mod;
            }
        }
    }
    ll inv = powMod(k, mod-2);
    for(auto x : cyclesize){
        // cout << x << " ";
        ll res = powMod(k-1, x);
        if(x%2) res -= k-1;
        else res += k-1;
        res %= mod;
        res += mod;
        res %= mod;
        // cout << res << " ";
        (ans *= res) %= mod;
        (ans *= inv) %= mod;
        (ans *= k-1) %= mod;
    }
    if(ok){
        // cout << "YES\n";
        ans *= powMod(k-1, mod-2);
        ans %= mod;
        ans *= k;
        ans %= mod;
    }
    cout << ans << "\n";
}

/*
1
11 11 10000
1 2
2 3
3 4
4 5
3 6
6 7
7 8
8 9
9 10
10 11
8 1

*/


int main()
{
    // fast_cin();    
    ll t = 1;
    cin >> t;
    for(int it=1; it<=t; it++)
    {
        //cout << "Case " << it << ": ";
        solve(it);
    }
    return 0;
}