#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;
debug(1.0*clock()/CLOCKS_PER_SEC);
return 0;
}