#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=35, mod=1e9+7;
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y%2) res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}int inv(int x){return qpow(x,mod-2);}
int fac[N], ifac[N];
void init(){
	fac[0]=1;
	rep(i,1,N-1){
		fac[i]=fac[i-1]*i%mod;
	}
	ifac[N-1]=inv(fac[N-1]);
	per(i,N-1,1){
		ifac[i-1]=ifac[i]*i%mod;
	}
}
int C(int m,int n){
	return fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}

vi gc(vi A){
	vi res(A.size());
	rep(i,0,(int)A.size()-1){
		int pw=1;
		rep(j,0,(int)A.size()-1){
			(res[i]+= pw*A[j] )%=mod;
			(pw*= i )%=mod;
		}
	}
	return res;
}
vi rgc(vi A){
	int n=A.size();
	vi prod{1};
	rep(i,0,n-1){
		prod.pb(0);
		per(j,(int)prod.size()-1,1){
			prod[j]=( prod[j]*(mod-i)+prod[j-1] )%mod;
		}
		prod[0]=prod[0]*(mod-i)%mod;
	}
	vi res(A.size());
	
	rep(i,0,n-1){
		vi cr=prod, cp(prod.size()-1);
		per(j,n,1){
			cp[j-1]=cr[j];
			(cr[j-1]+= i*cr[j] )%=mod;
		}
		int k=ifac[i]*ifac[n-1-i]%mod*((n-1-i)%2? mod-1: 1)%mod;
		rep(j,0,n-1){
			(res[j]+= A[i]*cp[j]%mod*k )%=mod;
		}
	}
	return res;
}
vi conv(vi A, vi B){
	vi res(A.size());
	rep(i,0,(int)A.size()-1){
		res[i]=A[i]*B[i]%mod;
	}
	return res;
}

void solve(){
	int n,m,k; cin>>n>>m>>k;
	int U=(1<<n)-1;
	vi adj(n), Adj(1<<n);
	rep(i,1,m){
		int u,v; cin>>u>>v;
		u--, v--;
		adj[u]|= 1<<v;
	}
	rep(s,1,U){
		int t=__builtin_ctz(s);
		Adj[s]=Adj[s-(1<<t)]|adj[t];
	}
	vi f(1<<n);
	vector<vi> F(1<<n, vi(n+1)), g(1<<n, vi(n+1)), h(1<<n, vi(n+1));
	f[0]=1;
	rep(s,1,U){
		rep(c,0,n){
			if((s>>c&1) && (adj[c]&s)==0){
				(f[s]+= f[s-(1<<c)] )%=mod;
			}
		}
	}
	rep(s,0,U){
		rep(i,0,n){
			F[s][i]=i*f[s]%mod;
		}
	}
	auto no_edge=[&](int S,int T){
		return (Adj[S]&T)==0;
	};
	fill(g[0].begin(), g[0].end(), mod-1);
	rep(s,1,U){
		int t=s-(1<<__builtin_ctz(s));
		for(int c=t; ; c=(c-1)&t){
			if(no_edge(c,s-c) && no_edge(s-c,c)){
				rep(i,0,n){
					(g[s][i]-= g[c][i]*F[s-c][i] )%=mod;
					if(g[s][i]<0){
						g[s][i]+= mod;
					}
				}
			}
			if(!c){
				break;
			}
		}
	}
	fill(h[0].begin(), h[0].end(), 1);
	rep(s,1,U){
		int t=s;
		for(int c=t; c; c=(c-1)&t){
			if(no_edge(s-c,c)){
				rep(i,0,n){
					(h[s][i]+= g[c][i]*h[s-c][i] )%=mod;
				}
			}
		}
	}
	h[U]=rgc(h[U]);
	vi T=gc(h[U]);
	int ans=0;
	rep(i,1,min(n,k+1)){
		(ans+= C(k+1, i)*h[U][i]%mod*fac[i] )%=mod;
	}
	(ans*= ifac[n+k]*fac[k]%mod )%=mod;
	cout<< ans <<'\n';
	
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	init();
	solve();
}