#include <bits/stdc++.h>
using namespace std;

const int sz = 404040, ljz = 1000000007, half = (ljz + 1) >> 1;
int Tm(int x, int y) {return (1ll * x * y) % ljz;}
void MOD(int &x){if (x >= ljz) x -= ljz; if (x < 0) x += ljz;}

#define next nnnnn
int N, M, k;
int node[sz], next[sz], to[sz], e;
void ins(int x, int y) {e++; next[e] = node[x]; node[x] = e; to[e] = y;}
namespace Hash {
  const int lxk = 765437;
  int f(int x, int y) {
    int s = (32523395 ^ (x * 2452455 + y * 4352902)) % lxk;
    if (s < 0) s = -s; return s;
  }
  int node[lxk], next[sz], X[sz], Y[sz], e;
  void ins(int x, int y) {
    if (x > y) swap(x, y); int s = f(x, y);
    e++; next[e] = node[s]; node[s] = e; X[e] = x; Y[e] = y;
  }
  int find(int x, int y) {
    if (x > y) swap(x, y); int s = f(x, y), j;
    for (j = node[s]; j; j = next[j]) if (X[j] == x && Y[j] == y) return 1;
    return 0;
  }
  void clr() {
    for (int i = 1; i <= e; i++) {
      node[f(X[i], Y[i])] = 0; next[i] = X[i] = Y[i] = 0;
    } e = 0;
  }
};
int deg[sz], two[sz], x[sz], y[sz];

void clr() {
  for (int i = 1; i <= N; i++) node[i] = deg[i] = 0;
  for (int i = 1; i <= e; i++) next[i] = to[i] = 0; e = 0;
  Hash::clr();
}

int tri() {
  int ans = 0;
  for (int i = 1; i <= N; i++)
    if (1ll * deg[i] * deg[i] <= M) {
      for (int j = node[i]; j; j = next[j])
	for (int k = next[j]; k; k = next[k])
	  if (Hash::find(to[j], to[k])) ans++;
    } else {
      for (int j = 1; j <= M; j++)
	if (Hash::find(i, x[j]) && Hash::find(i, y[j])) ans++;
    }
  return Tm(ans, 2);
}

void doit() {
  int i, j, a, ans; clr();
  scanf("%d %d %d", &N, &M, &k);
  for (a = 1; a <= M; a++) {
    scanf("%d %d", &i, &j); ins(i, j); ins(j, i);
    deg[i]++; deg[j]++; Hash::ins(i, j); x[a] = i; y[a] = j;
  }
  int twon = 1; for (int i = 1; i <= N; i++) MOD(twon <<= 1);
  int _1 = Tm(twon, half), _2 = Tm(_1, half), _3 = Tm(_2, half), _4 = Tm(_3, half), _5 = Tm(_4, half), _6 = Tm(_5, half);
  if (k == 1) {printf("%d\n", Tm(M, _2)); return;}
  int a22 = M, a23 = 0, a24;
  for (i = 1; i <= N; i++) MOD(a23 += Tm(deg[i], deg[i] - 1));
  MOD(a24 = Tm(M, M) - a22); MOD(a24 -= a23);
  if (k == 2) {
    ans = Tm(a22, _2); MOD(ans += Tm(a23, _3)); MOD(ans += Tm(a24, _4));
    printf("%d\n", ans); return;
  }
  int a32 = M, a33, a34, a35, a36, tr = tri();
  MOD(a33 = Tm(a23, 3) + tr);
  a34 = Tm(a24, 3);
  for (i = 1; i <= N; i++) MOD(a34 += Tm(Tm(deg[i], deg[i] - 1), deg[i] - 2));
  for (i = 1; i <= M; i++) MOD(a34 += Tm(6, Tm(deg[x[i]] - 1, deg[y[i]] - 1)));
  MOD(a34 -= Tm(tr, 3));
  a35 = tr;
  for (i = 1; i <= N; i++) {
    MOD(a35 += Tm(M - deg[i] + 2, Tm(deg[i], deg[i] - 1)));
    for (j = node[i]; j; j = next[j]) MOD(a35 -= Tm(2, Tm(deg[i] - 1, deg[to[j]])));
  }
  a35 = Tm(3, a35);
  a36 = Tm(Tm(M, M), M); MOD(a36 -= a32); MOD(a36 -= a33); MOD(a36 -= a34); MOD(a36 -= a35);
  ans = Tm(a32, _2); MOD(ans += Tm(a33, _3)); MOD(ans += Tm(a34, _4)); MOD(ans += Tm(a35, _5)); MOD(ans += Tm(a36, _6));
  printf("%d\n", ans);
}

int main() {int T; scanf("%d", &T); while (T--) doit(); return 0;}