#include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define inx2(u) int I2=h[(u)],v2=edge[I2].v;I2;I2=edge[I2].nx,v2=edge[I2].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1000010,Mod=1000000007,N=20; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;} int Pow(int x,int y){if(y<0)return 0;int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod;y>>=1;}return rt;} int n,m,k,ans,a[MAXN],b[MAXN],d[MAXN],C[N][N],vis[MAXN]; struct side{int u,v;}s[MAXN]; int slv3(){ int res=0; for(int i=1;i<=m;i++){ int u=s[i].u,v=s[i].v;if(d[u]<d[v])swap(u,v); add_side(u,v); } for(int i=1;i<=n;i++){ for(inx(i))vis[v]=1; for(inx(i)){ for(inx2(v))if(vis[v2])res++; } for(inx(i))vis[v]=0; } return res; } int slv4(int p3){ int res=0; for(int i=1;i<=n;i++)res+=d[i]*(d[i]-1)/2*(d[i]-2)/3%Mod,res%=Mod; // cout<<res<<endl; for(int i=1;i<=m;i++){ int u=s[i].u,v=s[i].v; res+=(d[u]-1)*(d[v]-1); } res+=Mod-3*p3%Mod; res%=Mod; return res; } int slv5(int p3){ for(int i=1;i<=m;i++){ int u=s[i].u,v=s[i].v;if(d[u]<d[v])swap(u,v); add_side(v,u); } int res=p3*3%Mod; for(int u=1;u<=n;u++){ res+=(m-d[u]+2)*(d[u]*(d[u]-1)/2%Mod)%Mod;res%=Mod; for(inx(u)){ res+=(d[u]-1)*(Mod-d[v])%Mod; res%=Mod; } } return res; } void slv(){ n=read(),m=read(),k=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(); d[u]++,d[v]++; s[i]={u,v}; } if(k==1){ printf("%lld",m*Pow(2,n-2)%Mod); } else if(k==2){ int cnt=0; ans=m%Mod*Pow(2,n-2)%Mod; for(int i=1;i<=n;i++)cnt+=d[i]*(d[i]-1),cnt%=Mod; ans+=cnt*Pow(2,n-3)%Mod;ans%=Mod; ans+=(m*m-cnt-m)*Pow(2,n-4)%Mod;ans%=Mod; printf("%lld",ans); } else{ int cnt=0,cnt2=m*(m-1)/2; for(int i=1;i<=n;i++)cnt+=d[i]*(d[i]-1)/2,cnt%=Mod; cnt2-=cnt; // cout<<cnt<<" "<<cnt2<<endl; cnt2*=6,cnt*=6; // cout<<cnt2<<endl;; int p3=slv3(),p4=slv4(p3)*6,p5=slv5(p3)*6; p3=p3*6; // cout<<cnt<<" "<<cnt2<<" "<<p3<<" "<<p4<<" "<<p5<<" "<<(m*m*m-p3-p4-p5-cnt-m-cnt2)<<endl; ans+=( cnt2%Mod*Pow(2,n-4)%Mod+ cnt%Mod*Pow(2,n-3)%Mod+ p3%Mod*Pow(2,n-3)%Mod+ p4%Mod*Pow(2,n-4)%Mod+ p5%Mod*Pow(2,n-5)%Mod+ (m*m*m-p3-p4-p5-cnt-m-cnt2)%Mod*Pow(2,n-6)%Mod )%Mod; ans+=m%Mod*Pow(2,n-2)%Mod; ans%=Mod; printf("%lld",ans); } } signed main(){ slv(); return 0; }