#include <bits/stdc++.h>
#define MOD 1000000007
int N,M,K,la[20],nii=1,ans,p[20],co[20],iv[20],v[20],aq,vv[20][20],s[20],dp[33333];
inline int pw(int a,int b) {
	int as=1;
	while(b) {
		if(b&1) as=1ll*as*a%MOD;
		a=1ll*a*a%MOD;b>>=1;
	}
	return as;
}
inline int ni(int a) {
	return pw(a,MOD-2);
}
int t[20],vq,pa[20],qq[20][20],dg[20];
inline int fr(int x) {
	while(x!=pa[x]) x=pa[x]=pa[pa[x]];
	return x;
}
inline int qd(int N) {
	bool zt=0;
	memset(dg,0,sizeof(dg));
	memset(qq,0,sizeof(qq));
	for(int i=N;i>=1;i--) {
		for(int j=i+1;j<=N;j++) {
			if(vv[i][j]&&co[i]!=co[j]) {
				qq[co[i]][co[j]]=1;
			} 
		}	
	}
	for(int i=1;i<=K+1;i++) for(int j=1;j<=K+1;j++) dg[j]+=qq[i][j];
	std::queue<int> q;
	for(int i=1;i<=K+1;i++) if(!dg[i]) q.push(i);
	int zz=0;
	while(!q.empty()) {
		int a=q.front();q.pop();zz++;
		for(int j=1;j<=N;j++) {
			if(qq[a][j]) {
				dg[j]--;
				if(!dg[j]) q.push(j);
			}
		}
	}
	if(zz!=K+1) return 1;	
	return 0;
}
inline int chk(void) {
	for(int i=1;i<=N;i++) pa[i]=i;
	for(int i=1;i<=N;i++) t[i]=(1<<i-1);
	for(int i=N;i>=1;i--) {
		for(int j=i+1;j<=N;j++) {
			if(vv[i][j]) {
				if(co[j]==co[i]) {
					if(fr(j)!=fr(i)) t[fr(i)]|=t[fr(j)],pa[fr(j)]=fr(i);
				}
			}
		}	
	}
	memset(v,0,sizeof(v));
	for(int i=1;i<=N;i++) {
		v[co[i]]++;
	}
	std::sort(v+1,v+K+2);
	int ans=1ll*p[K+1]*nii%MOD*iv[N]%MOD*p[K]%MOD,la=1;
	for(int i=1;i<=N;i++) if(pa[i]==i) ans=1ll*ans*dp[t[i]]%MOD,ans=1ll*ans*iv[__builtin_popcount(t[i])]%MOD;
	for(int i=2;i<=K+1;i++) {
		if(v[i]!=v[i-1]) {
			la=1;
		} else {
			la++;
			if(v[i]==0) ans=1ll*ans*iv[la]%MOD*p[la-1]%MOD;
		}
	}
	for(int i=1;i<=K+1;i++) ans=1ll*ans*p[v[i]]%MOD;
	return ans;
}
std::unordered_map<long long,int> asq;
int dfs(int n,int cl) {
	if(cl>K+1) return 0;
	if(qd(n-1)) return 0;
	if(n==N+1) {return chk();}
	long long hsh=n;
	if(vq) {
		int v2[20];memset(v2,0,sizeof(v2));
		for(int i=1;i<n;i++) {
			v2[i]=co[i];
		}
		std::sort(v2+1,v2+n);
		for(int i=1;i<n;i++) {
			hsh=(hsh*137ll+v2[i])%10000000000000007ll;
		}
		if(asq.find(hsh)!=asq.end()) return asq[hsh];
	}
	la[cl+1]=n;co[n]=cl+1;
	int ans=dfs(n+1,cl+1);
	for(int i=1;i<=cl;i++) {
		int tp=la[i];la[i]=n;co[n]=i;ans+=dfs(n+1,cl);la[i]=tp;
		ans%=MOD;
	}
	if(vq) asq[hsh]=ans;return ans;
}
signed main(void) {
	scanf("%d %d %d",&N,&M,&K);
	if(M==0) {
		printf("1");
		return 0;
	}
	bool zz=0;
	for(int i=1;i<=M;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		vv[a][b]=1;
		if(a!=1) zz=1;
	}
	for(int i=N+1;i<=N+K;i++) nii=1ll*nii*i%MOD;
	p[0]=iv[0]=1;
	for(int i=1;i<=N+1;i++) p[i]=1ll*p[i-1]*i%MOD,iv[i]=ni(p[i]);
	nii=ni(nii);
	dp[0]=1;
	for(int i=1;i<(1<<N);i++) {
		for(int j=1;j<=N;j++) {
			if((i>>j-1)&1) {
				bool zt=0;
				for(int k=j+1;k<=N;k++) {
					if(((i>>k-1)&1)&&vv[j][k]) zt=1;
				}
				if(!zt) dp[i]=(dp[i]+dp[i-(1<<j-1)])%MOD;
			}
		}
	}
	if(zz==0&&M==N-1) {
		vq=1;
	}
	printf("%d",dfs(1,0));
}