#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using ll = long long;

const int MOD = (int)1e9 + 7;
int n, m, k, ans, fac[55], inv_fac[55], bm_adj[25], bm_adj_or[(1 << 15) + 5], cnt[(1 << 15) + 5], dp[(1 << 15) + 5][25];
bool vis[25][25], have[25];
vector<int> good_bms, adj[25];

int exp_mod(int a, int b) {
	int r = 1;
	while (b) {
		if (b % 2 == 1) {
			r = (ll)r * a % MOD;
		}
		a = (ll)a * a % MOD;
		b /= 2;
	}
	return r;
}

void dfs(int u, bool cur_vis[]) {
	if (cur_vis[u]) {
		return;
	}
	cur_vis[u] = 1;
	for (auto v : adj[u]) {
		dfs(v, cur_vis);
	}
}

int nck(int n, int k) {
	if (k < 0 || k > n) {
		return 0;
	}
	return (ll)fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		u--;
		v--;
		adj[u].pb(v);
		bm_adj[u] |= (1 << v);
	}
	for (int bm = 1; bm < (1 << n); bm++) {
		int j = (bm & -bm);
		bm_adj_or[bm] = bm_adj_or[bm ^ j] | bm_adj[__builtin_ctz(j)];
	}
	for (int i = 0; i < n; i++) {
		dfs(i, vis[i]);
	}
	cnt[0] = 1;
	for (int bm = 1; bm < (1 << n); bm++) {
		vector<int> in_bm, not_in_bm;
		for (int i = 0; i < n; i++) {
			if (bm & (1 << i)) {
				in_bm.pb(i);
			} else {
				not_in_bm.pb(i);
			}
		}
		bool bad = 0;
		for (int i : in_bm) {
			for (int j : in_bm) {
				if (i == j) {
					continue;
				}
				for (int k : not_in_bm) {
					if (vis[i][k] && vis[k][j]) {
						bad = 1;
						break;
					}
				}
				if (bad) {
					break;
				}
			}
			if (bad) {
				break;
			}
		}
		if (!bad) {
			good_bms.pb(bm);
		}
		int is_source = bm;
		for (int j : in_bm) {
			is_source &= ~bm_adj[j];
		}
		for (int j = is_source; j; j -= (j & -j)) {
			cnt[bm] += cnt[bm ^ (j & -j)];
			if (cnt[bm] >= MOD) {
				cnt[bm] -= MOD;
			}
		}
	}
	dp[0][0] = 1;
	for (int bm = 1; bm < (1 << n); bm++) {
		for (int num = 1; num <= n; num++) {
			fill(have, have + n, 0);
			for (int j : good_bms) {
				if ((j & bm) != j) {
					continue;
				}
				int mn = __builtin_ctz(j);
				have[mn] = 1;
			}
			int target = -1;
			for (int j = 0; j < n; j++) {
				if (have[j]) {
					target = j;
					break;
				}
			}
			for (int j : good_bms) {
				if ((j & bm) != j || __builtin_ctz(j) != target) {
					continue;
				}
				int oth = bm ^ j;
				if (bm_adj_or[oth] & j) {
					continue;
				}
				//~ cout << "AT " << bm << ' ' << num << " TRY " << j << ' ' << cnt[j] << '\n';
				dp[bm][num] += (ll)dp[oth][num - 1] * cnt[j] % MOD;
				if (dp[bm][num] >= MOD) {
					dp[bm][num] -= MOD;
				}
			}
		}
	}
	fac[0] = inv_fac[0] = 1;
	for (int i = 1; i <= n + k; i++) {
		fac[i] = (ll)fac[i - 1] * i % MOD;
		inv_fac[i] = exp_mod(fac[i], MOD - 2);
	}
	for (int i = 1; i <= min(n, k + 1); i++) {
		dp[(1 << n) - 1][i] = (ll)dp[(1 << n) - 1][i] * fac[i] % MOD;
		//~ cout << "DP " << i << ' ' << dp[(1 << n) - 1][i] << '\n';
		int coeff = (ll)fac[i - 1] * nck(k, i - 1) % MOD * nck(k + 1, i) % MOD * fac[k - i + 1] % MOD;
		ans += (ll)dp[(1 << n) - 1][i] * coeff % MOD;
		if (ans >= MOD) {
			ans -= MOD;
		}
	}
	//~ cout << ans << '\n';
	cout << (ll)ans * inv_fac[n + k] % MOD << '\n';
}