#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
il ll qp(ll a,ll b){
    ll ans=1ll;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return ans;
}
il void add(ll &x,ll y){x=(x+y>=mod?x+y-mod:x+y);}
const int N=16;
int n,m,k,e[N][N],a[N*2],b[N],vis[N*2],p[N];ll fac[N*2],inv[N*2],f[1<<N],ans;
il void init(){
    fac[0]=1ll;for(int i=1;i<=n*2;++i) fac[i]=(fac[i-1]*1ll*i)%mod;
    inv[n*2]=qp(fac[n*2],mod-2ll);for(int i=n*2-1;i>=0;--i) inv[i]=(inv[i+1]*(i+1ll))%mod;
}
il ll C(int n,int m){return (n<0 || m<0 || n<m)?0ll:(fac[n]*inv[m]%mod*inv[n-m])%mod;}
int g[N][N],in[N];pii d[N];int cnt,id[N*2];
il void get(){
    int x,y,z,cc;queue<int> q;
    for(int i=1;i<=n;++i) p[i]=i;
    do{
        cc=1;
        for(int i=1;i<=n;++i) a[i]=p[i];
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) g[i][j]=0;
        for(int i=1;i<=n+k;++i) vis[i]=id[i]=0;
        for(int i=1;i<=k;++i){
            x=b[i];
            for(int j=n+i;j>x;--j) a[j]=a[j-1];
            a[x]=0;
        }
        cnt=0;
        for(int i=1;i<=n+k;++i){
            if(!a[i]) continue;
            x=i;while(x<n+k && a[x+1]) ++x;
            d[++cnt]={i,x};
            for(int j=i;j<=x;++j) id[a[j]]=cnt;
            i=x;
        }
        for(int i=1;i<=cnt;++i){
            x=d[i].fi,y=d[i].se;
            for(int j=x;j<=y;++j) for(int l=j+1;l<=y;++l) if(e[a[l]][a[j]]) {cc=0;break;}
            if(!cc) break;
        }
        if(!cc) continue;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(e[i][j] && id[i]!=id[j]) g[id[i]][id[j]]=1;
        for(int i=1;i<=cnt;++i) in[i]=0;
        for(int i=1;i<=cnt;++i)
            for(int j=1;j<=cnt;++j)
                if(g[i][j] && i!=j) ++in[j];
        for(int i=1;i<=cnt;++i) vis[i]=0;
        for(int i=1;i<=cnt;++i) if(!in[i]) q.push(i),vis[i]=1;
        while(q.size()){
            x=q.front();q.pop();
            for(int y=1;y<=cnt;++y){
                if(!g[x][y]) continue;
                if(vis[y]) continue;
                if(!(--in[y])) vis[y]=1,q.push(y);
            }
        }
        for(int i=1;i<=cnt;++i) if(in[i]) cc=0;
        if(cc) ++ans;
    }while(next_permutation(p+1,p+1+n));
}
void dfs(int x){
    if(x>k){get();return ;}
    for(int i=1;i<=n+x;++i) b[x]=i,dfs(x+1),b[x]=0;
}
il void ad(ll &x,ll y){x=(x+y>=mod?x+y-mod:x+y);}
ll h[N][N][N*2][N*2];
int x,y;ll u,v,w;
int main(){
    //freopen("timeline.in","r",stdin);
    //freopen("timeline.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);init();
    for(int i=1;i<=m;++i) scanf("%d%d",&x,&y),e[x][y]=1;
    if(!m){printf("1");exit(0);}
    if(!k){
        f[0]=1ll;int S=(1<<n);
        for(int i=0;i<S;++i){
            for(int j=0;j<n;++j){
                if((i>>j)&1) continue;
                x=1;
                for(int k=0;k<n;++k){
                    if(!((i>>k)&1)) continue;
                    if(e[j+1][k+1]) {x=0;break;}
                }
                if(x) add(f[i|(1<<j)],f[i]);
            }
        }
        printf("%lld",(f[S-1]*inv[n])%mod);
        exit(0);
    }
    if(n<=5){
        dfs(1);
        u=1ll;for(int i=1;i<=k;++i) u=(u*(n+i))%mod;
        printf("%lld",(ans*inv[n]%mod*qp(u,mod-2ll))%mod);
        exit(0);
    }
    x=0;for(int i=2;i<=n;++i) x+=e[1][i];
    if(m==n-1 && x==n-1){
        ans=(C(n+k-1,n-1)*fac[n-1]%mod*fac[k])%mod;
        if(k) ans=(ans+(n+k-1)*C(n+k-2,n-1)*fac[n-1]%mod*fac[k])%mod;
        u=1ll;for(int i=1;i<=k;++i) u=(u*(n+i))%mod;
        printf("%lld",(ans*inv[n]%mod*qp(u,mod-2ll))%mod);
        exit(0);
    }
    if(m==n*(n-1)/2){
        h[0][1][0][0]=1ll;
        for(int i=0;i<k;++i){
            for(int j=1;j<=i+1;++j){
                for(int u=0;u<=i;++u){
                    for(int v=0;v<=n+k;++v){
                        //h[i+1][j+1][u]=(h[i+1][j+1][u]+h[i][j][u]*(n-j))%mod;
                       //h[i+1][j][u+1]=(h[i+1][j][u+1]+h[i][j][u]*(u+2ll))%mod;
                       // h[i+1][j][u]=(h[i+1][j][u]+h[i][j][u]*)
                        add(h[i+1][j+1][u][v+2],(h[i][j][u][v]*(n-j))%mod);
                        add(h[i+1][j][u+1][v],h[i][j][u][v]*(u+2ll)%mod);
                        add(h[i+1][j][u][v+1],h[i][j][u][v]*v%mod);
                    }
                }
            }
        }
        for(int i=1;i<=k+1;++i){
            ll x=0ll;
            for(int j=0;j<=n+k;++j)
                for(int u=0;u<=n+k;++u)
                    add(x,h[k][i][j][u]);
            ans=(ans+x*fac[i])%mod;
        }
        u=1ll;for(int i=1;i<=k;++i) u=(u*(n+i))%mod;
        printf("%lld",(ans*inv[n]%mod*qp(u,mod-2ll))%mod);
        exit(0);
    }
    return 0;
}