#include<bits/stdc++.h>
// #define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define fr first
#define se second
#define ford(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) (int)(s.size())
#define all(s) s.begin(),s.end()
#define vii vector<pair<int,int> >
#define re return
// #define mod 998244353
using namespace std;
const int mod=1e9+7;
ll q_p(ll x,ll y){
    ll res=1;
    x%=mod;
    while(y){
        if(y%2){
            res=res*x;
            res%=mod;
        }
        y/=2;
        x=x*x;
        x%=mod;
    }
    re res;
}
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
int n,m,k;
bool g[15][17];
int ng[(1<<15)];
int f[(1<<15)][17],h[(1<<15)][17];
int topo[(1<<15)];
void add(int &x,int y){
    x+=y;
    if(x>=mod)
    x-=mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    rep(i,m){
        int a,b;
        cin>>a>>b;a--,b--;
        g[a][b]=1;
        ng[(1<<b)]|=(1<<a);
    }
    forn(i,1,(1<<n)){
        int lb=(i&(-i));
        ng[i]=(ng[i^lb]|ng[lb]);
    }
    topo[0]=1;
    rep(i,(1<<n)){
        rep(j,n){
            if(!(i&(1<<j)))
            continue;
            bool ok=1;
            rep(kk,n){
                if((i&(1<<kk))&&g[kk][j])
                ok=0;
            }
            if(ok)
            add(topo[i],topo[i^(1<<j)]);
        }
    }
    rep(i,(1<<n)){
        h[0][0]=1;
        if(i)
        forn(j,1,k+2){
            int lb=(i&(-i));
            int ni=(i^lb);
            for(int s=(ni);s;s=((s-1)&(ni)))
            if((!(ng[s|lb]&(ni^s)))&&(!(ng[ni^s]&(s|lb)))){
                add(h[i][j],1ll*h[ni^s][j-1]*topo[s|lb]%mod);
            }
            if((!(ng[lb]&(ni)))&&(!(ng[ni]&(lb))))
            add(h[i][j],1ll*h[ni][j-1]*topo[lb]%mod);
        }
    }
    rep(i,(1<<n))
    rep(j,k+2)
    if((j&1)==0){
        if(h[i][j])
        h[i][j]=mod-h[i][j];
    }
    
    f[0][0]=1;
    forn(s,1,(1<<n)){
        for(int i=s;i;i=((i-1)&s)){
            if(ng[s^i]&(i))
            continue;
            rep(j,n+1)
            if(h[i][j])
            rep(kk,(n+1)-j){
                add(f[s][j+kk],1ll*f[s^i][kk]*h[i][j]%mod);
            }
        }
    }
    int ans=0;
    forn(i,1,k+2){
        ll now=f[(1<<n)-1][i];
        for(int j=1;j<=1+k;j++)
        now=now*j%mod;
        for(int j=1;j<=k+1-i;j++)
        now=now*q_p(j,mod-2)%mod;
        for(int j=1;j<=k;j++)
        now=now*j%mod;
        add(ans,now);
    }
    for(int j=1;j<=n+k;j++)
    ans=1ll*ans*q_p(j,mod-2)%mod;
    cout<<ans;
    re 0;
}