#include <bits/stdc++.h>

using namespace std;

const int mod = 1000000007;

int modmul(int64_t a, int64_t b) {
    return static_cast<int>(a * b % mod);
}
int modadd(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}
int modsub(int a, int b) {
    return a - b < 0 ? a - b + mod : a - b;
}

int modpow(int e, int p) {
    int r = 1;
    while (p) {
        if (p & 1) r = modmul(r, e);
        e = modmul(e, e);
        p >>= 1;
    }
    return r;
}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int N, M, K;
        cin >> N >> M >> K;

        vector<int> inv(M + 1), fac(M + 1), ifac(M + 1);
        inv[1] = 1;
        for (int i = 2; i <= M; i++)
            inv[i] = modmul(inv[mod % i], (mod - mod / i));
        fac[0] = ifac[0] = 1;
        for (int i = 1; i <= M; i++) {
            fac[i] = modmul(fac[i-1], i);
            ifac[i] = modmul(ifac[i-1], inv[i]);
        }

        vector<vector<int>> g(N);
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }

        int cycle_cnt = 0;
        vector<int> vis(N);
        vector<int> dep(N);
        vector<int> cycle;
        const auto dfs = [&](auto self, int i, int f) -> void {
            vis[i] = true;
            for (int j: g[i]) {
                if (not vis[j]) {
                    dep[j] = dep[i] + 1;
                    self(self, j, i);
                } else if (j != f && dep[j] < dep[i]) {
                    cycle.emplace_back(dep[i] - dep[j] + 1);
                    cycle_cnt += cycle.back();
                }
            }
        };

        dfs(dfs, 0, -1);
        const int bridge = M - cycle_cnt;

        const int invk = modpow(K, mod - 2);
        const auto C = [&](int n, int k) {
            if (k < 0 || n < k) return 0;
            return modmul(fac[n], modmul(ifac[k], ifac[n-k]));
        };
        int ans = 1;
        for (int sz: cycle) {
            // cerr << "sz = " << sz << endl;
            int sum = 0;
            int prod = 1;
            for (int i = 0; i <= sz; i++) {
                if (i % 2 == 0)
                    sum = modadd(sum, modmul(prod, C(sz, i)));
                else
                    sum = modsub(sum, modmul(prod, C(sz, i)));
                if (i <= sz - 2) {
                    prod = modmul(prod, invk);
                }
            }
            ans = modmul(ans, sum);
        }
        // cerr << "bridge = " << bridge << '\n';
        for (int i = 0; i < bridge; i++) {
            int sum = modsub(1, invk);
            ans = modmul(ans, sum);
        }
        ans = modmul(ans, modpow(K, N));
        cout << ans << '\n';
    }
}