#include<bits/stdc++.h> #define int long long using namespace std; int n,m,k; int a[30][30]; int ans=0; int p[30]; const int mod=1e9+7; void dfs(int u,int z){ if(u==n+1){ int mm=0; for(int i=1;i<z;i++){ for(int j=i+1;j<z;j++){ if(a[p[i]][p[j]]) mm++; } } if(k==1) ans+=mm; else if(k==2) ans+=mm*mm%mod; else ans+=mm*mm*mm%mod; ans%=mod; return; } dfs(u+1,z); p[z]=u; dfs(u+1,z+1); } signed main(){ cin>>n>>m>>k; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; a[x][y]=1; a[y][x]=1; } dfs(1,1); cout<<ans<<endl; }