#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,k,deg[maxn]; struct nd { int x,y; }d[maxn]; int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int g1(){ return m*1ll*qp(2,n-2)%mod; } int g2(){ up(i,1,m)deg[d[i].x]++,deg[d[i].y]++; int res=0; ll all=m*1ll*(m-1)/2; up(i,1,n){ all-=deg[i]*1ll*(deg[i]-1)/2; if(deg[i]>=2)(res+=deg[i]*1ll*(deg[i]-1)/2%mod*1ll*qp(2,n-3)%mod)%=mod; }all%=mod; if(n>=4)(res+=all*1ll*qp(2,n-4)%mod)%=mod; return res; } vector<int>E[maxn],vec[maxn]; int vis[maxn]; ll cycle_3(){ up(i,1,m){ int x=d[i].x,y=d[i].y; if(deg[x]!=deg[y]){ if(deg[x]>deg[y])swap(x,y); }else if(x>y)swap(x,y); E[y].p_b(x); } ll res=0; up(i,1,n){ for(int x:E[i])vis[x]=1; for(int x:E[i])for(int y:E[x])if(vis[y])res++; for(int x:E[i])vis[x]=0; } return res; } int g3(){ up(i,1,n)deg[i]=0; up(i,1,m)deg[d[i].x]++,deg[d[i].y]++; int all=0; int ans=cycle_3(); int tmp=ans; if(n>=3)(all+=ans)%=mod,ans=ans*1ll*qp(2,n-3)%mod; if(n>=4){ int sum=0; up(i,1,n){ if(deg[i]<3)continue; int v=deg[i]*1ll*(deg[i]-1)%mod*1ll*(deg[i]-2)%mod*1ll*qp(6,mod-2)%mod; (sum+=v)%=mod; } int vv=0; up(i,1,m){ int x=d[i].x,y=d[i].y; if(deg[x]<=1||deg[y]<=1)continue; int v=(deg[x]-1)*1ll*(deg[y]-1)%mod; (vv+=v)%=mod; } vv=(vv-tmp*3ll%mod+mod)%mod; (sum+=vv)%=mod; (ans+=sum*1ll*qp(2,n-4)%mod)%=mod; (all+=sum)%=mod; /*int ss=0; up(i,1,m){ up(j,i+1,m){ up(k,j+1,m){ set<int>st; st.insert(d[i].x),st.insert(d[i].y); st.insert(d[j].x),st.insert(d[j].y); st.insert(d[k].x),st.insert(d[k].y); if(st.size()==4)cout<<"! "<<d[i].x<<" "<<d[i].y<<" "<<d[j].x<<" "<<d[j].y<<" "<<d[k].x<<" "<<d[k].y<<endl,ss++; } } } cout<<"test "<<sum<<" "<<ss<<endl; exit(0); (ans+=ss*1ll*qp(2,n-4)%mod)%=mod; (all+=ss)%=mod;*/ } if(n>=5){ /*int ss=0; up(i,1,m){ up(j,i+1,m){ up(k,j+1,m){ set<int>st; st.insert(d[i].x),st.insert(d[i].y); st.insert(d[j].x),st.insert(d[j].y); st.insert(d[k].x),st.insert(d[k].y); if(st.size()==5)ss++; } } } (ans+=ss*1ll*qp(2,n-5)%mod)%=mod; (all+=ss)%=mod;*/ up(i,1,m){ int x=d[i].x,y=d[i].y; vec[x].p_b(y),vec[y].p_b(x); } int ss=0; up(i,1,n){ if(deg[i]<2)continue; int f=(m+2-deg[i])*1ll*(deg[i]*1ll*(deg[i]-1)/2%mod)%mod; for(int x:vec[i])f=(f-deg[x]*1ll*(deg[i]-1)%mod+mod)%mod; (ss+=f)%=mod; } (ss+=tmp*3ll%mod)%=mod; //cout<<"! "<<ss<<endl; (ans+=ss*1ll*qp(2,n-5)%mod)%=mod; (all+=ss)%=mod; } if(n>=6){ int ss=m*1ll*(m-1)%mod*1ll*(m-2)%mod*1ll*qp(6,mod-2)%mod; ss=(ss-all+mod)%mod; (ans+=ss*1ll*qp(2,n-6)%mod)%=mod; } return ans; } void slv(){ n=read(),m=read(),k=read(); up(i,1,m)d[i].x=read(),d[i].y=read(); ll s1=g1();ll s2=g2();ll s3=g3(); if(k==1)cout<<s1; else if(k==2)cout<<(s2*2+s1)%mod; else cout<<(6*s3+6*s2+s1)%mod; } int main(){ //freopen("head.in","r",stdin); //freopen("head.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }