//  Copyright 2020 Nikita Golikov

#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;
using ui64 = uint64_t;

#ifdef GOLIKOV
mt19937_64 rng(566);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

template <typename T>
T rnd_helper(T from, T to, true_type) {
  return uniform_int_distribution<T>(from, to)(rng);
}

template <typename T>
T rnd_helper(T from, T to, false_type) {
  return uniform_real_distribution<T>(from, to)(rng);
}

template <typename T>
T rnd(T from, T to) {
  return rnd_helper(from, to, is_integral<T>{});
}

template <typename A, typename B, typename Cmp>
bool set_min(A &x, B const &y, Cmp &&cmp) {
  if (cmp(y, x)) {
    x = y;
    return true;
  }
  return false;
}

template <typename A, typename B>
bool set_min(A &x, B const &y) {
  return set_min(x, y, less<typename common_type<A, B>::type>{});
}

template <typename A, typename B>
bool set_max(A &x, B const &y) {
  return set_min(x, y, greater<typename common_type<A, B>::type>{});
}

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename K, typename V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag,
                         tree_order_statistics_node_update>;

//  https://codeforces.com/blog/entry/62393
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t
        FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return static_cast<size_t>(splitmix64(x + FIXED_RANDOM));
  }
};

#ifdef __cpp_deduction_guides
template <typename F>
struct rec_fun {
  F fun;

  rec_fun(F&& fun_) : fun(std::forward<F>(fun_)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return fun(*this, std::forward<Args>(args)...);
  }
};
#endif

#ifdef __cpp_inline_variables
template <typename T>
inline constexpr auto type_min = numeric_limits<T>::min();

template <typename T>
inline constexpr auto type_max = numeric_limits<T>::max();
#endif

//  fast alloc
#if 0
int const MAX_MEM = 1e8;
int mpos = 0;
char mem[MAX_MEM];
void* operator new(size_t n) {
  mpos += n;
  return (void*)(mem + mpos - n);
}
void operator delete (void*) noexcept {}
#endif

//  pragmas
#if 0
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("unroll-loops")
#endif

template <int MOD>
struct modular {
  int val{};

  static int norm(i64 x) {
    int res = -MOD <= x && x < MOD ? x : (int) (x % MOD);
    if (res < 0) {
      res += MOD;
    }
    return res;
  }

  modular() = default;
  modular(int x, bool do_norm = false) : val(do_norm ? norm(x) : x) {}
  modular(i64 x) : val(norm(x)) {}

  int to_int() const {
    return val;
  }
  modular& operator+=(modular other) {
    val += other.val;
    if (val >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  friend modular operator+(modular x, modular y) {
    return x += y;
  }
  modular& operator-=(modular other) {
    val -= other.val;
    if (val < 0) {
      val += MOD;
    }
    return *this;
  }
  friend modular operator-(modular x, modular y) {
    return x -= y;
  }
  modular& operator++() {
    if (++val == MOD) {
      val = 0;
    }
    return *this;
  }
  modular& operator--() {
    if (--val < 0) {
      val = MOD - 1;
    }
    return *this;
  }
  friend modular operator*(modular x, modular y) {
    return modular{(i64) x.val * y.val};
  }
  modular operator*=(modular other) {
    return *this = *this * other;
  }
  friend bool operator==(modular x, modular y) {
    return x.to_int() == y.to_int();
  }
  friend bool operator!=(modular x, modular y) {
    return x.to_int() != y.to_int();
  }
  modular operator-() const {
    return 0 - *this;
  }
  friend istream& operator>>(istream& in, modular& x) {
    return in >> x.val;
  }
  friend ostream& operator<<(ostream& out, modular x) {
    return out << x.val;
  }
  explicit operator bool() const {
    return bool(val);
  }
};

template <int MOD>
modular<MOD> power(modular<MOD> x, i64 deg) {
  if (!x) {
    return !deg;
  }
  deg %= MOD - 1;
  if (deg < 0) {
    deg += MOD - 1;
  }
  modular<MOD> res = 1;
  while (deg) {
    if (deg & 1) {
      res *= x;
    }
    x *= x;
    deg /= 2;
  }
  return res;
}

template <int MOD>
modular<MOD> inv(modular<MOD> x) {
  return power(x, -1);
}

template <int MOD>
modular<MOD> operator/(modular<MOD> x, modular<MOD> y) {
  return x * inv(y);
}

template <int MOD>
modular<MOD>& operator/=(modular<MOD>& x, modular<MOD> other) {
  return x = x / other;
}

int const MOD = (int) 1e9 + 7;
using mint = modular<MOD>;

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  mint k;
  cin >> n >> m >> k;

  struct edge {
    int to, id;

    edge(int to_, int id_) : to(to_), id(id_) {}
  };
  vector<pair<int, int>> edges(m);
  vector<vector<edge>> graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    graph[u].emplace_back(v, i);
    graph[v].emplace_back(u, i);
    edges[i] = {u, v};
  }

  vector<bool> used(n);
  vector<int> up(n, 2 * n + 5), d(n);
  std::function<void(int, int)> dfs = [&](auto v, auto p) {
    used[v] = true;
    if (v != p) {
      d[v] = d[p] + 1;
    }
    for (auto e : graph[v]) {
      auto u = e.to;
      if (u == p) {
        continue;
      }
      if (used[u]) {
        up[v] = min(up[v], d[u]);
      } else {
        dfs(u, v);
        up[v] = min(up[v], up[u]);
      }
    }
  };
  for (int i = 0; i < n; ++i) {
    if (!used[i]) {
      dfs(i, i);
    }
  }
  fill(used.begin(), used.end(), 0u);
  vector<int> comp(m);
  int cur_comp = 0;
  function<void(int, int, int)> dfs2 =
      [&](auto v, auto p, auto c){
        used[v] = true;
        for (auto e : graph[v]) {
          auto u = e.to;
          auto i = e.id;
          if (u == p) {
            continue;
          }
          if (!used[u]) {
            if (up[u] < d[v]) {
              comp[i] = c;
              dfs2(u, v, c);
            } else {
              comp[i] = ++cur_comp;
              dfs2(u, v, comp[i]);
            }
          } else if (d[u] < d[v]) {
            comp[i] = c;
          }
        }
      };
  for (int i = 0; i < n; ++i) {
    if (!used[i]) {
      dfs2(i, i, cur_comp);
      ++cur_comp;
    }
  }
  auto compressed = comp;
  sort(compressed.begin(), compressed.end());
  compressed.erase(unique(compressed.begin(), compressed.end()),
                   compressed.end());
  int ncomps = (int) compressed.size();
  vector<vector<int>> comp_to_edges(ncomps);
  for (int i = 0; i < m; ++i) {
    auto id = lower_bound(compressed.begin(), compressed.end(), comp[i])
        - compressed.begin();
    comp_to_edges[id].push_back(i);
  }

  vector<mint> pw(m + 1);
  pw[0] = 1;
  for (int i = 1; i <= m; ++i) {
    pw[i] = pw[i - 1] * k;
  }

  auto gcd = [](int a, int b) {
    while (b) {
      a %= b;
      swap(a, b);
    }
    return a;
  };
  auto ways_cycle = [&](int len) {
    mint ans = 0;
    for (int i = 1; i <= len; ++i) {
      ans += pw[gcd(i, len)];
    }
    return ans / mint(len);
  };
  auto ways_comp = [&](int len) {
    mint cur = k + len - 1;
    mint ans = 1;
    for (int i = 0; i < len; ++i) {
      ans *= cur;
      ans /= mint(i + 1);
      --cur;
    }
    return ans;
  };
  auto solve = [&](int i) {
    vector<int> deg(n);
    for (auto e : comp_to_edges[i]) {
      ++deg[edges[e].first];
      ++deg[edges[e].second];
    }
    bool is_comp = false;
    for (int v = 0; v < n; ++v) {
      if (deg[v] && deg[v] != 2) {
        is_comp = true;
        break;
      }
    }
    if (is_comp) {
      return ways_comp(comp_to_edges[i].size());
    }
    return ways_cycle(comp_to_edges[i].size());
  };
  mint ans = 1;
  for (int i = 0; i < ncomps; ++i) {
    ans *= solve(i);
  }
  cout << ans << '\n';

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}


Measured memory_bytes: 3664