#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,m,k;
vector<int>e[N];
int c[N],ans=0;
void dfs(int u) {
    if(u>n){
        ans=(ans+1)%mod;
        return;
    }
    for(int i=1;i<=k;++i){
        bool co=true;
        for(int v:e[u]){
            if(c[v]==i){
                co=false;
                break;
            }
        }
        if(co){
            c[u]=i;
            dfs(u+1);
            c[u]=0;
        }
    }
}
int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i(1);i<=m;++i){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
    dfs(1);
    cout<<ans<<endl;
    return 0;
}