#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; } bool tg[N]; vector<int> E[N]; int calc(){ for(int i=1;i<=m;i++){ if(du[rel[i].fi]<=du[rel[i].se]) E[rel[i].fi].push_back(rel[i].se); else E[rel[i].se].push_back(rel[i].fi); }int ans=0; for(int i=1;i<=n;i++){ for(auto ed:E[i]) tg[ed]=1; for(auto ed:E[i]){ for(auto eg:E[ed]){ if(tg[eg]) ans=(ans+1)%mod; } }for(auto ed:E[i]) tg[ed]=0; }return ans; }void slv3(){ for(int i=1;i<=m;i++){ if(rel[i].fi>rel[i].se) swap(rel[i].fi,rel[i].se); du[rel[i].fi]++;du[rel[i].se]++; }int all=0; all=1ll*m*(m-1)*(m-2)%mod; int ct3,ct4,ct5,ct6; int r3=calc(); //cout<<r3<<' '; ct4=0,ct5=0; for(int i=1;i<=m;i++){//lian ct4=(ct4+1ll*(du[rel[i].fi]-1)*(du[rel[i].se]-1)%mod)%mod; //cout<<ct4<<' '; }ct4=(ct4+mod-3ll*r3%mod)%mod; for(int i=1;i<=m;i++){ int cnt=du[rel[i].fi]+du[rel[i].se]-2; int cnt2=m-1-cnt; ct5=(ct5+1ll*cnt*cnt2%mod)%mod; //cout<<ct5<<' '; }ct5=(ct5+mod-2ll*ct4%mod)%mod;ct5=3ll*ct5%mod; ct4=6ll*ct4%mod; //cout<<ct4<<' '; for(int i=1;i<=n;i++){//jvhua ct4=(ct4+1ll*(du[i]-2)*(du[i]-1)*du[i]%mod)%mod; }//cout<<ct4<<' '; r3=6ll*r3%mod; ct6=(all-(1ll*r3+ct4+ct5)%mod+mod)%mod; int ans=0; if(n>=3) ans=(ans+1ll*r3*p2[n-3])%mod; if(n>=4) ans=(ans+1ll*ct4*p2[n-4])%mod; if(n>=5) ans=(ans+1ll*ct5*p2[n-5])%mod; if(n>=6) ans=(ans+1ll*ct6*p2[n-6])%mod; 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+3ll*p2[n-3]*cnt%mod)%mod; if(n>=4) ans=(ans+3ll*p2[n-4]*cnt2%mod)%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; }