#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 1'000'000'007;
int qexp(int a, int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return res;
}
int inv(int x){
	return qexp(x,mod-2);
}
int F[30];
typedef pair<int,int>pi;
vector<pi>edges;
int32_t main(){
	F[0]=1;
	for(int i=1;i<30;i++){
		F[i]=F[i-1]*i%mod;
	}
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		edges.push_back({a,b});
	}
	int S=n+k;
	vector<int>choices;
	for(int i=0;i<1<<S;i++){
		if(__builtin_popcount(i) == k){ // cuts
			choices.push_back(i);
		}
	}
	int tot=choices.size();
	int ans=0;
	for(auto x:choices){
		vector<int>vec;
		for(int i=1;i<=n;i++)vec.push_back(i);
		int ways=0;
		do{
			vector<vector<int>>V;
			vector<int>cur;
			int idx=0;
			for(int j=0;j<S;j++){
				if((x & (1<<j)) == 0){//not a cut
					cur.push_back(vec[idx++]);
				} else{
					V.push_back(cur);
					cur.clear();
				}
			}
			if(cur.size())V.push_back(cur);
			bool can=0;
			do{
				if(can)break;
				vector<int>cc;
				for(auto vv:V){
					for(auto x:vv){
						cc.push_back(x);
					}
				}
				can=1;
				for(auto e:edges){
					//e.first happen before e.second
					int ef=-1,es=-1;
					for(int x=0;x<cc.size();x++){
						if(cc[x]==e.first)ef=x;
						if(cc[x]==e.second)es=x;
					}
					if(e.first<e.second);
					else can=0;
				}
				
			} while(next_permutation(V.begin(),V.end()));
			if(can)ans++;
		}while(next_permutation(vec.begin(),vec.end()));
		
	}
	cout<<ans*inv(F[n])%mod*inv(tot)%mod;
					
	
}