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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

const int MOD = 1e9 + 7;
const int MX = 100;

namespace Mod {
    int fact[MX], ifact[MX];

    ll fpow(ll a, ll b){
        ll res = 1;
        for(a %= MOD; b; b >>= 1){
            if(b & 1) res = res * a % MOD;
            a = a * a % MOD;
        }
        return res;
    }

    inline ll modInv(ll a){
        return fpow(a, MOD-2);
    }

    inline ll choose(ll a, ll b){
        return (ll) fact[a] * ifact[b] % MOD * ifact[a-b] % MOD;
    }

    void initFact(){
        fact[0] = 1;
        for(int i = 1; i < MX; i++) fact[i] = (ll) fact[i-1]*i % MOD;
        ifact[MX-1] = modInv(fact[MX-1]);
        for(int i = MX-1; i > 0; i--) ifact[i-1] = (ll) ifact[i]*i % MOD;
    }
}
using namespace Mod;

const int MN = 15;
const int MP = 1 << MN;
int n, m, k, mask;
int adjMat[MN];
bitset<MP> isGood[MP];
int dp[MN][MP];

void genIsGood(){
    FR(s, 1<<n){
        int rem = mask ^ s;
        FR(i, n) if((s >> i) & 1) rem &= ~adjMat[i];
        for(int s2 = rem; s2; s2 = (s2-1) & rem) isGood[s][s2] = true;
        isGood[s][0] = true;
    }
}

void genDp0(){
    dp[0][0] = 1;
    FOR(s, 1, 1<<n){
        ll v = 0;
        FR(i, n) if((s >> i) & 1){
            int rem = s ^ (1 << i);
            if(!(adjMat[i] & rem)) v += dp[0][rem];
        }
        dp[0][s] = v % MOD;
    }
}

void genDp(int cuts){
    FOR(s, 1, 1<<n){
        ll v = 0;
        for(int s1 = (s-1) & s; s1; s1 = (s1-1) & s){
            int s2 = s ^ s1;
            v += (ll) dp[0][s1] * dp[cuts-1][s2] * (isGood[s1][s2] || isGood[s2][s1]);
        }
        dp[cuts][s] = v % MOD;
    }
}

void spec(){
    ll num = 0;
    FR(i, min(n, k+1)){
        int comps = i+1;
        num += (1LL << i) * fact[comps] % MOD;
    }
    num %= MOD;
    ll denom = (ll) fact[n+k] * ifact[k] % MOD;
    cout << num * modInv(denom) % MOD << '\n';
    exit(0);
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    FR(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adjMat[b] |= 1 << a;
    }
    mask = (1 << n) - 1;

    if(m == n*(n-1)/2) spec();

    genIsGood();
    genDp0();
    FOR(i, 1, min(n, k+1)) genDp(i);

    //FR(s, 1<<n) dbgArr(isGood[s], 1<<n);
    //FR(i, min(n, k+1)) dbgArr(dp[i], 1<<n);

    initFact();
    ll num = 0;
    FR(c, min(n, k+1)){
        num += choose(k+1, c+1) * dp[c][mask] % MOD;
    }
    num %= MOD;

    ll denom = (ll) fact[n+k] * ifact[k] % MOD;
    dbg(num);
    dbg(denom);
    cout << num * modInv(denom) % MOD << '\n';
}