#include <bits/stdc++.h>
#define il inline
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(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
il void del(int &x,int y){x=(x<y?x-y+mod:x-y);}
const int N=16;
int n,m,k,S,e[N][N],pc[1<<N],to[1<<N],lg[1<<N],a[N],h[1<<N],g[1<<N][N],f[1<<N],ans,fac[50],inv[50],G[1<<N];
int F[N],b[N],c[N];
il int ck(int x,int y){//check whether if y doesnt has some edge to x
	return (to[y]&x)==0;
}
il void init(){
	int x,y,z,u,v,w;
	for(int i=2;i<S;++i) lg[i]=lg[i>>1]+1;
	for(int i=1;i<S;++i) pc[i]=pc[i-(i&-i)]+1;
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) if(e[i][j]) a[i]|=(1<<j);
	for(int i=1;i<S;++i) to[i]=to[i-(i&-i)],x=lg[i&-i],to[i]|=a[x];
	fac[0]=1ll;for(int i=1;i<=n*2;++i) fac[i]=(1ll*fac[i-1]*i)%mod;
	inv[n*2]=qp(fac[n*2],mod-2ll);for(int i=n*2-1;i>=0;--i) inv[i]=(1ll*inv[i+1]*(i+1ll))%mod;
}
il ll calc(ll X){
	ll x,y,z,u,v,w,ret=0;
	x=1ll;for(int s=0;s<S;++s) G[s]=f[s]=0;
	for(int i=1;i<=n;++i){
		x=(x*X)%mod;
		for(int s=0;s<S;++s){
			y=(g[s][i]*x)%mod;if(!(i&1)) y=mod-y;
			add(G[s],y);
		}
	}
	f[0]=1ll;
	for(int s=1;s<S;++s)
		for(int t=s;t;t=(t-1)&s) if(ck(t,s^t)&&f[s^t]&&G[t]) f[s]=(f[s]+1ll*f[s^t]*G[t])%mod;
	return f[S-1];
}
il void solve(){
	ll x,y,z,u,v,w;
	F[0]=1ll;
	for(int i=1;i<=n;++i)
		for(int j=i;j>=0;--j) F[j]=((j?F[j-1]:0ll)+1ll*(mod-i)*F[j])%mod;
	for(int i=0;i<=n;++i){
		x=(1ll*a[i]*inv[i]%mod*inv[n-i])%mod;if((n-i)&1) x=mod-x;
		if(!i){for(int j=0;j<=n;++j) b[j]=F[j+1];}
		else{
			y=qp(1ll*i,mod-2ll),b[0]=mod-1ll*F[0]*y%mod;
			for(int j=1;j<=n;++j) b[j]=(1ll*(b[j-1]-F[j]+mod)*y)%mod;
			for(int j=n;j;--j) b[j]=b[j-1];b[0]=0;
		}
		for(int j=0;j<=n;++j) c[j]=(c[j]+1ll*x*b[j])%mod;
	}
}
int x,y,z,w;
int main(){
	//freopen("P10221_18.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);S=(1<<n);
	for(int i=1;i<=m;++i) scanf("%d%d",&x,&y),--x,--y,e[x][y]=1;
	init();
	h[0]=1ll;
	for(int i=1;i<S;++i){
		if(i==(i&-i)){h[i]=1ll;continue;}
		for(int j=0;j<n;++j){
			if(!((i>>j)&1)) continue;
			if(ck(i^(1<<j),(1<<j))) add(h[i],h[i^(1<<j)]);
		}
	}
	g[0][0]=1ll;
	for(int i=1;i<=n;++i)
		for(int s=1;s<S;++s)
			for(int t=s;t;t=(t-1)&s)
				if(ck(t,s^t)&ck(s^t,t)&((t>>lg[s])&1)) g[s][i]=(g[s][i]+1ll*h[t]*g[s^t][i-1])%mod;
	for(int i=1;i<=n;++i) a[i]=calc(1ll*i);a[0]=0;
	solve();
	for(int i=1;i<=k+1;++i) ans=(ans+1ll*c[i]*inv[k+1-i])%mod;
	printf("%lld",1ll*ans*fac[k]%mod*fac[k+1]%mod*inv[n+k]%mod);
	return 0;
}