#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;
const ll MOD = 1e9+7;

int TC, N, M;
ll K;
vector<int> adj[MAXN+10];

ll dp[MAXN+10], dp2[MAXN+10];

int cnt;
int dfn[MAXN+10], low[MAXN+10];

void dfs(int now, int bef)
{
    dfn[now]=++cnt;
    low[now]=dfn[now];
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(dfn[nxt]==0)
        {
            dfs(nxt, now);
            low[now]=min(low[now], low[nxt]);
        }
        else
        {
            low[now]=min(low[now], dfn[nxt]);
        }
    }
}

int bcnt;
bool vis[MAXN+10];
int A[MAXN+10];
void bcc(int now, int bef, int col)
{
    vis[now]=true;
    A[col]++;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(vis[nxt]) continue;
        if(low[nxt]>=dfn[nxt]) bcc(nxt, now, ++bcnt);
        else bcc(nxt, now, col);
    }
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    scanf("%d", &TC);
    while(TC--)
    {
        scanf("%d%d%lld", &N, &M, &K);
        for(int i=1; i<=M; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        dp[1]=K; dp2[1]=K-1;
        dp[2]=K*(K-1)%MOD; dp2[2]=(K-1)*(K-1)%MOD;
        ll t=K-1;
        for(int i=3; i<=N; i++)
        {
            t=t*(K-1)%MOD;
            dp[i]=K*t%MOD-dp[i-1];
            dp2[i]=(K-1)*t%MOD-dp2[i-1];
            dp[i]=(dp[i]%MOD+MOD)%MOD;
            dp2[i]=(dp2[i]%MOD+MOD)%MOD;
        }

        dfs(1, 1);
        bcc(1, 1, ++bcnt);

        ll ans=dp[A[1]];
        for(int i=2; i<=bcnt; i++) ans=ans*dp2[A[i]]%MOD;
        printf("%lld\n", ans);

        for(int i=1; i<=N; i++)
        {
            adj[i].clear();
            dfn[i]=low[i]=vis[i]=0;
            A[i]=0;
            dp[i]=0; dp2[i]=0;
        }

        cnt=0; bcnt=0;
    }
}