#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;
}

void solve(){
	int n,m,k; cin>>n>>m>>k;
	int U=(1<<n)-1;
	vi adj(n);
	rep(i,1,m){
		int u,v; cin>>u>>v;
		u--, v--;
		adj[u]|= 1<<v;
	}
	vi f(1<<n);
	vector<vi> g(1<<n, vi(k+2,0)), h(1<<n, vi(k+2,0));
	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,1,U){
		// (f[s]*= ifac[__builtin_popcount(s)] )%=mod;
	// }
	auto no_edge=[&](int S,int T){
		rep(i,0,n-1){
			if((S>>i&1) && (adj[i]&T)){
				return false;
			}
		}
		return true;
	};
	g[0][0]=mod-1, h[0][0]=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,k){
					(g[s][i+1]+= (mod-g[c][i])*f[s-c] )%=mod;
				}
			}
			if(!c){
				break;
			}
		}
	}
	rep(s,1,U){
		int t=s;
		for(int c=t; c; c=(c-1)&t){
			if(no_edge(s-c,c)){
				rep(i,1,k+1){
					rep(j,0,k+1-i){
						(h[s][i+j]+= g[c][i]*h[s-c][j] )%=mod;
					}
				}
			}
		}
	}
	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();
}