#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};

constexpr unsigned MO = 1000000007;
using Mint = ModInt<MO>;


constexpr int LIM = 110;
Mint inv[LIM], fac[LIM], invFac[LIM];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (0 <= k && k <= n) {
    assert(n < LIM);
    return fac[n] * invFac[k] * invFac[n - k];
  } else {
    return 0;
  }
}


template <class T> vector<vector<T>> zeta(const vector<T> &as) {
  const int n = __lg(as.size());
  assert(static_cast<int>(as.size()) == 1 << n);
  vector<vector<T>> zas(1 << n, vector<T>(n + 1, 0));
  for (int h = 0; h < 1 << n; ++h) zas[h][__builtin_popcount(h)] = as[h];
  for (int i = 0; i < n; ++i) for (int h = 0; h < 1 << n; ++h) {
    if (!(h & 1 << i)) {
      for (int k = 0; k <= n; ++k) zas[h | 1 << i][k] += zas[h][k];
    }
  }
  return zas;
}

template <class T> vector<T> moebius(vector<vector<T>> zas) {
  const int n = zas[0].size() - 1;
  assert(static_cast<int>(zas.size()) == 1 << n);
  for (int i = 0; i < n; ++i) for (int h = 0; h < 1 << n; ++h) {
    if (!(h & 1 << i)) {
      for (int k = 0; k <= n; ++k) zas[h | 1 << i][k] -= zas[h][k];
    }
  }
  vector<T> as(1 << n);
  for (int h = 0; h < 1 << n; ++h) as[h] = zas[h][__builtin_popcount(h)];
  return as;
}


vector<Mint> mul(const vector<Mint> &as, const vector<Mint> &bs) {
  const int n = as.size() - 1;
  vector<Mint> cs(n + 1, 0);
  for (int i = 0; i <= n; ++i) for (int j = 0; i + j <= n; ++j) {
    cs[i + j] += as[i] * bs[j];
  }
  return cs;
}
vector<Mint> power(const vector<Mint> &as, Mint e) {
  /*
    b = a^e
    b' / b = e a' / a
    a b' = e a' b
  */
  const int n = as.size() - 1;
  assert(as[0].x == 1);
  vector<Mint> bs(n + 1, 0);
  bs[0] = 1;
  for (int i = 1; i <= n; ++i) {
    Mint sum = 0;
    for (int j = 1; j <= i; ++j) sum += ((e + 1) * j - i) * as[j] * bs[i - j];
    bs[i] = inv[i] * sum;
  }
  return bs;
}


int uf[LIM];
int root(int u) {
  return (uf[u] < 0) ? u : (uf[u] = root(uf[u]));
}
bool connect(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


struct UnluckyNumber {
  int numberOfColourings(int n, int m, int k, int z, vector <int> x, vector <int> y) {
    prepare();
    
    for (int i = 0; i < m; ++i) {
      --x[i];
      --y[i];
    }
    
    const Int numSelfs = (z % 2 == 0) ? 1 : 0;
    const Int numPairs = ((min(z - 2, 2 * k - z) + 1) - numSelfs) / 2;
    const Int numOthers = k - 2 * numPairs - numSelfs;
    
    // two colors which cannot be adjacent
    vector<Mint> fs(1 << n, 0);
    for (int p = 0; p < 1 << n; ++p) {
      fill(uf, uf + n, -1);
      for (int i = 0; i < m; ++i) {
        if ((p & 1 << x[i]) && (p & 1 << y[i])) {
          connect(x[i], y[i]);
        }
      }
      fs[p] = 1;
      for (int u = 0; u < n; ++u) {
        if (p & 1 << u) {
          if (uf[u] < 0) {
            fs[p] *= 2;
          }
        }
      }
    }
    
    // independent set
    vector<Mint> gs(1 << n, 0);
    for (int p = 0; p < 1 << n; ++p) {
      bool ok = true;
      for (int i = 0; i < m; ++i) {
        ok = ok && !((p & 1 << x[i]) && (p & 1 << y[i]));
      }
      if (ok) {
        gs[p] += 1;
      }
    }
    
    // any
    vector<Mint> hs(1 << n, 1);
    
    // f^numPairs g^numSelfs h^numOthers
    auto zfs = zeta(fs);
    auto zgs = zeta(gs);
    auto zhs = zeta(hs);
    for (int p = 0; p < 1 << n; ++p) {
      zfs[p] = mul(mul(power(zfs[p], numPairs), power(zgs[p], numSelfs)), power(zhs[p], numOthers));
    }
    const auto res = moebius(zfs);
    
    const Mint ans = res[(1 << n) - 1];
    return ans.x;
  }
};


int brute(int n, int m, int k, int z, vector <int> x, vector <int> y) {
  int ans = 0;
  for (int p = 0; p < 1 << (3 * n); ++p) {
    vector<int> col(n);
    for (int u = 0; u < n; ++u) {
      col[u] = ((p >> (3 * u)) & 7) + 1;
    }
    bool ok = true;
    for (int u = 0; u < n; ++u) {
      ok = ok && (1 <= col[u] && col[u] <= k);
    }
    for (int i = 0; i < m; ++i) {
      ok = ok && (col[x[i] - 1] + col[y[i] - 1] != z);
    }
    if (ok) {
      ++ans;
    }
  }
  return ans;
}

int main() {
  cout << UnluckyNumber().numberOfColourings(3, 3, 4, 4, {1, 2, 3}, {2, 3, 1}) << endl;
  cout << UnluckyNumber().numberOfColourings(18, 18, 987654321, 1000000000, {1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 16, 17}, {2, 3, 1, 5, 6, 7, 4, 9, 10, 11, 12, 10, 11, 12, 11, 12, 17, 18}) << endl;
  
  /*
  for (int n = 2; n <= 5; ++n) {
    for (int k = 1; k <= 8; ++k) {
      for (int z = 2; z <= 2 * k; ++z) {
        cerr << "n = " << n << ", k = " << k << ", z = " << z << " ..." << endl;
        for (int p = 0; p < 1 << (n * (n - 1) / 2); ++p) {
          vector<int> x, y;
          int pos = 0;
          for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) {
            if (p & 1 << pos) {
              x.push_back(u + 1);
              y.push_back(v + 1);
            }
            ++pos;
          }
          int m = x.size();
          const int brt = brute(n, m, k, z, x, y);
          const int res = UnluckyNumber().numberOfColourings(n, m, k, z, x, y);
          if (brt != res) {
            cerr << "n = " << n << ", m = " << m << ", k = " << k << ", z = " << z << endl;
            cerr << "x = "; pv(x.begin(), x.end());
            cerr << "y = "; pv(y.begin(), y.end());
            cerr << "brt = " << brt << endl;
            cerr << "res = " << res << endl;
            assert(false);
          }
        }
      }
    }
  }
  */
  return 0;
}