#include <bits/stdc++.h>
using namespace std;
vector<vector<char>> g;
map<long long, bool> dp;
void brute(int n, vector<int> &p) {
  int x = find(p.begin(), p.end(), -1) - p.begin();
  if (x == int(p.size())) {
    vector<vector<char>> dp2(1 << n, vector<char>(n));
    vector<int> pos1(n), pos2(n);
    for (int i = 0; i < int(p.size()); i++) {
      pos1[p[i]] = pos2[p[i]];
      pos2[p[i]] = i;
    }
    for (int i = 0; i < int(n); i++)
      if (g[pos1[i]][pos2[i]]) dp2[1 << i][i] = true;
    for (int mask = 0; mask < int(1 << n); mask++)
      for (int i = 0; i < int(n); i++)
        if (dp2[mask][i]) {
          for (int j = 0; j < int(n); j++)
            if (!((mask >> j) & 1)) {
              dp2[mask | (1 << j)][j] |=
                  (g[pos1[i]][pos1[j]] && g[pos2[i]][pos2[j]]);
              dp2[mask | (1 << j)][j] |=
                  (g[pos1[i]][pos2[j]] && g[pos2[i]][pos1[j]]);
            }
        }
    for (int i = 0; i < int(n); i++)
      if (dp2[(1 << n) - 1][i]) {
        long long num = 0;
        for (int x : p) num = num * 6 + x;
        dp[num] = true;
        break;
      }
    return;
  }
  for (int y = x + 1; y < int(p.size()); ++y)
    if (p[y] == -1) {
      p[x] = p[y] = n;
      brute(n + 1, p);
      p[x] = p[y] = -1;
    }
}
bool dfs(vector<int> p) {
  vector<int> used(int(p.size()), -1);
  int cnt = 0;
  for (int i = 0; i < int(p.size()); i++)
    if (used[p[i]] == -1) used[p[i]] = cnt++;
  long long num = 0;
  for (int &x : p) {
    x = used[x];
    num = num * 6 + x;
  }
  if (dp.count(num)) return dp[num];
  bool res = false;
  vector<int> cur(cnt);
  for (int i = 0; i < int(p.size()); i++) ++cur[p[i]];
  for (int i = 0; i < int(p.size()); i++)
    if (cur[p[i]] > 2) {
      int x = p[i];
      for (int j = i + 1; j < int(p.size()); ++j)
        if (p[j] == p[i]) {
          p[i] = p[j] = cnt;
          if (dfs(p)) {
            res = true;
            break;
          }
          p[i] = p[j] = x;
        }
      break;
    }
  return dp[num] = res;
}
void brute2(int n, vector<int> &p) {
  int x = find(p.begin(), p.end(), -1) - p.begin();
  if (x == int(p.size())) {
    dfs(p);
    return;
  }
  for (int i = 0; i < int(n + 1); i++) {
    for (int y = x + 1; y < int(p.size()); ++y)
      if (p[y] == -1) {
        p[x] = p[y] = i;
        brute2(max(n, i + 1), p);
        p[x] = p[y] = -1;
      }
  }
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  g.resize(n, vector<char>(n));
  for (int _ = 0; _ < int(m); _++) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v, --u;
    g[v][u] = g[u][v] = 1;
  }
  vector<int> cur(n, -1);
  brute(0, cur);
  brute2(0, cur);
  vector<long long> fact(k + 1);
  fact[0] = 1;
  for (int i = 1; i <= k; ++i) fact[i] = fact[i - 1] * i;
  long long ans = 0;
  for (auto it : dp)
    if (it.second) {
      long long num = it.first;
      long long mx = 1;
      while (num) {
        mx = max(mx, num % 6 + 1);
        num /= 6;
      }
      if (mx <= k) {
        ans += fact[k] / fact[k - mx];
      }
    }
  printf("%lld\n", ans);
  return 0;
}
