#include <cstdio>

const int MAXN = 1e5 + 10;
const int MAXM = 1e5 + 10;
const int MOD = 1e9 + 7;

struct EDGE {
  int v, next;
} edge[MAXM << 1];

int head[MAXN], edgeNum;
void AddEdge(int u, int v) {
  edge[++edgeNum] = {v, head[u]};
  head[u] = edgeNum;
}

int n, m, k;
int color[MAXN];
int cnt;

bool canPlace(int u, int target) {
  for (int i = head[u]; i; i = edge[i].next) {
    if (color[edge[i].v] == target) return false;
  }
  return true;
}

void dfs(int u) {
  if (u > n) {
    if (++cnt == MOD) cnt = 0;
    return ;
  }
  for (int i = 1; i <= k; ++i) if (canPlace(u, i)) {
    color[u] = i;
    dfs(u + 1);
    color[u] = 0;
  }
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
  #endif

  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1, a, b; i <= m; ++i) {
    scanf("%d %d", &a, &b);
    AddEdge(a, b);
    AddEdge(b, a);
  }

  dfs(1);

  printf("%d\n", cnt);
  
  return 0;
}