#include<bits/stdc++.h>
using namespace std;
const int N=15,P=1e9+7;
int n,m,k,h[1<<N],g[1<<N][N+2],f[1<<N],nowg[1<<N],in[N],out[N];
vector<int> spd[1<<N],aspd[1<<N];
inline int fadd(int x,int y){
	return (x+y>=P?x+y-P:x+y);
}
inline int fminus(int x,int y){
	return (x>=y?x-y:x+P-y);
}
inline int get(int x,int y){
	int ret=0;
	for(int i=0,mul=1;i<n;i++,mul*=3){
		if(x&(1<<i))	ret+=mul;
		if(y&(1<<i))	ret+=mul*2;
	}
	return ret;
}
inline void getp(){
	for(int s=0;s<(1<<n);s++){
		int now=0;
		for(int i=0;i<n;i++) if(s&(1<<i))	now|=(1<<i),now|=out[i];
		now=(1<<n)-1-now;
		for(int t=now;t;t=(t-1)&now)	spd[s|t].push_back(t);
		now=(1<<n)-1-now;
		for(int i=0;i<n;i++) if(s&(1<<i))	now|=in[i];
		now=(1<<n)-1-now;
		for(int t=now;t;t=(t-1)&now)	aspd[s|t].push_back(t);
	}
	// for(int s=0;s<(1<<n);s++)	cout<<aspd[s].size()<<endl;
}
inline void geth(){
	h[0]=1;
	for(int s=1;s<(1<<n);s++){
		for(int i=0;i<n;i++) if((s&(1<<i))&&!((s-(1<<i))&in[i]))
			h[s]=fadd(h[s],h[s-(1<<i)]);
		// cout<<h[s]<<endl;
	}
}
inline void getg(){
	g[0][0]=1;
	for(int s=1;s<(1<<n);s++){
		int mx=0;
		for(int i=0;i<n;i++) if(s&(1<<i))	mx=i;
		for(int t:aspd[s])	if((t&(1<<mx)))	for(int i=1;i<=n;i++)
			g[s][i]=fadd(g[s][i],1ll*g[s-t][i-1]*h[t]%P);
		// cout<<g[s][1]<<endl;
		// for(int t:aspd[s])	cout<<s<<" "<<t<<endl;
	}
}
inline int getf(int x){
	for(int s=0;s<(1<<n);s++){
		nowg[s]=0;
		for(int i=0,mul=1;i<=n;i++,mul=1ll*mul*x%P){
			if(i&1)	nowg[s]=fadd(nowg[s],1ll*g[s][i]*mul%P);
			else	nowg[s]=fminus(nowg[s],1ll*g[s][i]*mul%P);
		}
	}
	f[0]=1;
	for(int s=1;s<(1<<n);s++){
		f[s]=0;
		// cout<<spd[s].size()<<endl;
		// for(int t:spd[s])	cout<<s<<" "<<t<<endl;
		for(int t:spd[s]){
			f[s]=fadd(f[s],1ll*f[s-t]*nowg[t]%P);
			// cout<<s<<" "<<t<<" "<<f[s-t]<<" "<<nowg[t]<<" "<<f[s]<<endl;
		}
	}
	// cout<<"-"<<endl;
	return f[(1<<n)-1];
}
inline int solve(){
	auto inv=[&](const int aaa){
		int aa=aaa,nn=P-2,ret=1;
		for(;nn;nn>>=1,aa=1ll*aa*aa%P)	if(nn&1)	ret=1ll*ret*aa%P;
		return ret;
	};
	vector<int> y(0),sum(n+1,0),now(0);
	for(int i=0;i<=n;i++)	y.push_back(getf(i));
	// for(int i:y)	cout<<i<<" ";
	// cout<<endl;
	for(int i=0;i<=n;i++){
		int nowk=y[i];
		for(int j=0;j<=n;j++) if(j!=i)	nowk=1ll*nowk*inv(fminus(i,j))%P;
		now.clear(),now.push_back(nowk);
		for(int j=0;j<=n;j++) if(j!=i){
			now.push_back(0);
			for(int t=int(now.size())-1;t>0;t--)
				now[t]=fminus(now[t],1ll*j*now[t-1]%P);
		}
		for(int j=0;j<=n;j++)	sum[j]=fadd(sum[j],now[j]);
	}
	reverse(sum.begin(),sum.end());
	int ans=0;
	for(int i=1,mul=k+1;i<=min(n,k+1);i++,mul=1ll*mul*(k-i+2)%P)
		ans=fadd(ans,1ll*sum[i]*mul%P);
	for(int i=1;i<=k;i++)	ans=1ll*ans*i%P;
	for(int i=1;i<=n+k;i++)	ans=1ll*ans*inv(i)%P;
	return ans;
}
int main(){
	// freopen("P10221_18.in","r",stdin);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;x--,y--;
		out[x]|=(1<<y),in[y]|=(1<<x);
	}
	getp();
	geth();
	getg();
	cout<<solve()<<endl;
	return 0;
}