#include<bits/stdc++.h> using namespace std; #define fr first #define sc second #define int long long const int N=2e5+10,M=1e9+7; int n,m,k,deg[N],ans,cnt;bool son[N]; pair<int,int>E[N]; int read(){ char c=getchar();int d=0,op=1; while(c>'9'||c<'0'){if(c=='-')op=-1;c=getchar();} while(c<='9'&&c>='0'){d*=10;d+=c-'0';c=getchar();} return d*op; } struct Edge{int v,nx;}e[N<<1];int CNT,h[N]; void add(int u,int v){e[++CNT]={v,h[u]};h[u]=CNT;} int ksm(int a,int b){ if(b<0)return 0; int ans=1,base=a; while(b>0){ if(b&1)ans=ans*base%M; base=base*base%M;b>>=1; }return ans; } void count_ring(){ for(int i=1;i<=m;i++){ int u=E[i].fr,v=E[i].sc; if(deg[u]>deg[v]){add(u,v);} if(deg[u]<deg[v]){add(v,u);} if(deg[u]==deg[v]){ if(u<v)add(v,u); else add(u,v); } } for(int u=1;u<=n;u++){ for(int i=h[u],v=e[i].v;i>0;i=e[i].nx,v=e[i].v){son[v]=1;} for(int i=h[u],v=e[i].v;i>0;i=e[i].nx,v=e[i].v){ for(int j=h[v],w=e[j].v;j>0;j=e[j].nx,w=e[j].v){ if(son[w])cnt++; } } for(int i=h[u],v=e[i].v;i>0;i=e[i].nx,v=e[i].v){son[v]=0;} } } signed main(){ n=read();m=read();k=read(); //m^k可以看做在m条边中，选择k条（可重）的方案数 int u,v; for(int i=1;i<=m;i++){ u=read();v=read(); E[i]={u,v};deg[u]++;deg[v]++; } if(k==1){ ans=ksm(2,n-2)*m%M; printf("%lld\n",ans);return 0; } if(k==2){ int res=m*m%M; //两次选同一条： ans+=m*ksm(2,n-2)%M;ans%=M; res=(res-m+M)%M; // cout<<ans<<" "<<res<<endl; //两次选的边有一个共同点 for(int i=1;i<=n;i++){ // cout<<deg[u]<<" "<<deg[u]-1<<" "<<ksm(2,n-3)<<" "<<deg[u]*(deg[u]-1)%M*ksm(2,n-3)%M<<endl; ans+=deg[i]*(deg[i]-1)%M*ksm(2,n-3)%M;ans%=M; res=(res-(deg[i]*(deg[i]-1)%M)+M)%M; // cout<<ans<<" "<<res<<endl; } // cout<<ans<<" "<<res<<endl; //两次所选的是没有共同点的两条边 ans+=res*ksm(2,n-4)%M;ans%=M; printf("%lld\n",ans); return 0; } if(k==3){ int res=m*m%M*m%M,Res=m*m%M; //三次所选的是同一条边 ans+=m*ksm(2,n-2)%M;ans%=M; res=(res-m+M)%M;Res=(Res-m+M)%M; //三次中有两次选同一条边 int a=0; for(int i=1;i<=n;i++){ a+=deg[u]*(deg[u]-1)%M*ksm(2,n-3)%M;a%=M; Res=(Res-(deg[u]*(deg[u]-1)%M)+M)%M; } a+=Res*ksm(2,n-4)%M;a%=M; ans+=a*3%M;ans%=M; //三次选的是不同的边 //三元环 count_ring();res=(res-cnt+M)%M; ans=(ans+cnt*ksm(2,n-3)%M*6%M)%M; //菊花图 int b=0; for(int i=1;i<=n;i++){ int k=deg[i]*(deg[i]-1)%M*(deg[i]-2)%M; b=(b+k)%M; } ans=(ans+k*ksm(2,n-4))%M; res=(res-b+M)%M; //一条链 int c=0; for(int i=1;i<=m;i++){ int u=E[i].fr,v=E[i].sc; int k=(deg[u]-1)*(deg[v]-1)%M; c=(c+k)%M; } c=(c-3*cnt%M+M)%M; ans=(ans+c*ksm(2,n-4)%M+M)%M; res=(res-c+M)%M; //两条链 int d=0; for(int i=1;i<=n;i++){ d=(d+deg[i]*(deg[i]-1)%M*(m-2)%M)%M; } d=((d-b-2*c-2*cnt)%M+M)%M; ans=(ans+d*ksm(2,n-5)%M)%M; res=(res-d+M)%M; //三条链 ans=(ans+res*ksm(2,k-6)%M)%M; printf("%lld\n",ans); } return 0; }