#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=17,M=1<<15,mod=1e9+7;
int n,m,k,U,to[M];
ll qpow(ll x,ll y=mod-2,ll ans=1){
	for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
	return ans;
}
int f[M][N],g[M],h[M][N],C[N][N];
void calc(int *y,int *res){
	static int f[N];
	fill(res,res+1+n,0);
	for(int i=0;i<=n;i++){
		memset(f,0,sizeof f),f[0]=1;
		int val=y[i];
		for(int j=0;j<=n;j++)if(j^i){
			for(int k=n;k>=0;k--){
				f[k]=(1ll*f[k]*(mod-j)+(k?f[k-1]:0))%mod;
			}
			val=val*qpow((i-j+mod)%mod)%mod;
		}
		for(int j=0;j<=n;j++){
			res[j]=(res[j]+1ll*val*f[j])%mod;
		}
	}
}
int main(){
	cin>>n>>m>>k,U=(1<<n)-1;
	for(int u,v;m--;){
		cin>>u>>v,to[1<<u-1]|=1<<v-1;
	}
	for(int S=1;S<=U;S++){
		to[S]=to[S^(S&-S)]|to[S&-S];
	}
	for(int i=0;i<=k+1;i++){
		for(int j=C[i][0]=1;j<=i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	g[0]=1;
	for(int S=0;S<U;S++){
		for(int i=0;i<n;i++)if(~S>>i&1){
			if(to[1<<i]&S)continue;
			g[S|1<<i]=(g[S|1<<i]+g[S])%mod;
		}
	}
	for(int i=0;i<=n;i++)h[0][i]=mod-1;
	for(int S=1;S<=U;S++){
		for(int T=S;T;--T&=S)if(T&S&-S){
			if((to[T]&(S^T))||(to[S^T]&T))continue;
			for(int i=0;i<=n;i++){
				h[S][i]=(h[S][i]+1ll*h[S^T][i]*g[T]%mod*(mod-i))%mod;
			}
		}
	}
	for(int i=0;i<=n;i++)f[0][i]=1;
	for(int S=1;S<=U;S++){
		for(int T=S;T;--T&=S){
			if(to[T]&(S^T))continue;
			for(int i=0;i<=n;i++)f[S][i]=(f[S][i]+1ll*f[S^T][i]*h[T][i])%mod;
		}
	}
	static int res[N];
	calc(f[U],res);
	int ans=0;
	for(int i=1,fac=1;i<=n;i++){
		fac=1ll*fac*i%mod;
		ans=(ans+1ll*res[i]*fac%mod*C[k+1][i])%mod;
	}
	int mul=1;
	for(int i=1;i<=n;i++)mul=1ll*mul*(k+i)%mod;
	ans=ans*qpow(mul)%mod;
	cout<<ans<<endl;
	return 0;
}