#include<bits/stdc++.h>
# define int long long
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define dg ((1 << n) - 1)
# define N 20
# define P 33005
# define mod 1000000007
using namespace std;

int power(int a, int p)
{
	int ans = 1;
	for (; p; p >>= 1) {if (p & 1) (ans *= a) %= mod; (a *= a) %= mod;}
	return ans;
}
int n, m, k, b[N], fb[N], fac[105], inv[105], inc[105];
bitset < P > can[P], ok;
int tp[P], ud[P][N], dp[P][N], ans;
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	rep(i, 1, m) {int u, v; cin >> u >> v; --u, --v; b[u] |= (1 << v), fb[v] |= (1 << u);}
	fac[0] = inv[0] = inc[1] = 1; rep(i, 1, 100) fac[i] = fac[i - 1] * i % mod;
	inv[100] = power(fac[100], mod - 2); for (int i = 99; i; --i) inv[i] = inv[i + 1] * (i + 1) % mod, inc[i + 1] = fac[i] * inv[i + 1] % mod;
	rep(i, 0, dg) can[0][i] = can[i][0] = 1;
	rep(i, 1, dg)
	{
		int p = 0; rep(j, 0, n - 1) if (i & (1 << j)) {p = j; break;}
		int x = (i ^ dg);
		for (int j = x; j; j = ((j - 1) & x)) {can[i][j] = (can[i ^ (1 << p)][j] & !(fb[p] & j));}
	}
	tp[0] = 1;
	rep(i, 1, dg) rep(j, 0, n - 1) if ((i & (1 << j)) && !(fb[j] & (i ^ (1 << j)))) (tp[i] += tp[i ^ (1 << j)]) %= mod;
	ud[0][0] = 1;
	rep(i, 1, dg) for (int x = i; x; x = ((x - 1) & i)) if (can[x][i ^ x] && can[i ^ x][x]) rep(j, 1, k + 1) (ud[i][j] += tp[x] * ud[i ^ x][j - 1] % mod * inc[j]) %= mod;
	dp[0][0] = 1;
	rep(i, 1, dg) for (int x = i; x; x = ((x - 1) & i)) if (can[x][i ^ x])
	rep(j, 1, k + 1) {rep(t, 1, j) dp[i][j] += ((t & 1) ? 1 : -1) * ud[x][t] * dp[i ^ x][j - t]; ((dp[i][j] %= mod) += mod) %= mod;}
	rep(i, 1, k + 1) (ans += dp[dg][i] * fac[k] % mod * fac[k + 1] % mod * inv[k + 1 - i]) %= mod;
	cout << ans * inv[n + k] % mod << '\n';
	return 0;
}