#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=1e5+9,V=1.5e6+9,mod=1e9+7; int c[V]; int sp(int a,int b){ int x=1; while(b--) x=1ll*a*x%mod; return x; }int n,m,k;pii rel[N]; int du[N]; int p2[N]; void slv1(){ cout<<1ll*p2[n-2]*m%mod; }void slv2(){ for(int i=1;i<=m;i++){ du[rel[i].fi]++;du[rel[i].se]++; }int ans=0; for(int i=1;i<=m;i++){ ans=(ans+p2[n-2])%mod; int cnt=du[rel[i].fi]+du[rel[i].se]-2; int cnt2=m-1-cnt; if(n>=3) ans=(ans+1ll*p2[n-3]*cnt%mod)%mod; if(n>=4) ans=(ans+1ll*p2[n-4]*cnt2%mod)%mod; }cout<<ans; }void slv3(){ for(int i=1;i<=m;i++){ int stt=0; stt|=1<<(rel[i].fi-1);stt|=1<<(rel[i].se-1); c[stt]++; }int v=1<<n; for(int i=0;i<n;i++){ for(int j=0;j<v;j++){ if((j>>i)&1) c[j]+=c[j-(1<<i)]; } }int ans=0; for(int i=0;i<v;i++){ ans=(ans+sp(c[i],k))%mod; }cout<<ans; } int main(){ cin>>n>>m>>k; for(int i=1;i<=m;i++){ cin>>rel[i].fi>>rel[i].se; } p2[0]=1;for(int i=1;i<=n;i++) p2[i]=p2[i-1]*2%mod; if(k==1) slv1(); else if(k==2) slv2(); else slv3(); return 0; }