#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define CLR(x,y) memset(x,y,sizeof(x))
#define SQ(x) ((x)*(x))
#define ALL(x) (x).begin(),(x).end()
#define LL long long
const int Size = 1000055;
const LL mod = 1000000007;
int N, M, K;
int Time = 0;
vector<int> Graph[Size];
int disc[Size], low[Size];
int ap[Size];
int vis[Size], par[Size];
LL res = 0;
LL SIZE[Size];
int ID[Size];
int color = 1;
int totalAP = 0;
void AP(int cur) {
disc[cur] = low[cur] = ++Time;
vis[cur] = 1;
int child = 0;
vector<int> adj;
for (int i = 0; i < (int) Graph[cur].size(); i++) {
int v = Graph[cur][i];
LL prvTime = Time;
if (vis[v] == 0) {
par[v] = cur;
child++;
AP(v);
bool f = false;
if (par[cur] == -1 && child > 1) {
ap[cur] = 1;
f = true;
}
low[cur] = min(low[v], low[cur]);
if (par[cur] != -1 && low[v] >= disc[cur]) {
ap[cur] = 1;
f = true;
}
if(f == true){ /// There is a sub component which is connected to the main graph by edge cur-v
adj.pb(Time - prvTime);
/// Time - prvTime = the size of this sub component
}
} else if (v != par[cur]) {
low[cur] = min(disc[v], low[cur]);
}
}
if(ap[cur] == 1) totalAP++;
if(adj.size() == 0) return;
LL sizeOfOther = 0;
for(int i = 0;i<adj.size();i++){
sizeOfOther += adj[i];
}
LL sizeOfCurSubGraph = SIZE[ID[cur]] - sizeOfOther - 1;
adj.pb(sizeOfCurSubGraph);
for(int i = 0;i<adj.size();i++){
LL sz = adj[i];
/// No of ways to select (P,V) for current articulation point
LL add = sz * (SIZE[ID[cur]] - sz - 1);
add %= mod;
res += add;
res %= mod;
}
}
void DFS(int cur){
ID[cur] = color;
SIZE[color]++; /// Size of the current component
for(int i = 0;i<Graph[cur].size();i++){
int v = Graph[cur][i];
if(ID[v] != -1) continue;
DFS(v);
}
}
void solve() {
CLR(SIZE,0);
CLR(ID,-1);
/// Update color and size of different component in the graph.
for(int i = 1;i<=N;i++){
if(ID[i] != -1) continue;
DFS(i);
color++;
}
for(int i = 0;i<Size;i++){
disc[i] = low[i] = ap[i] = vis[i] = 0;
par[i] = -1;
}
for (int i = 1; i <= N; i++) {
if (vis[i] == 0) {
AP(i);
}
}
}
int main () {
int u,v;
scanf("%d %d %d", &N, &M, &K);
for (int i = 0; i < M; i++) {
scanf("%d %d", &u, &v );
Graph[u].pb(v);
Graph[v].pb(u);
}
solve();
printf("%lld\n",res);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIENMUih4LHkpIG1lbXNldCh4LHksc2l6ZW9mKHgpKQojZGVmaW5lIFNRKHgpICgoeCkqKHgpKQojZGVmaW5lIEFMTCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBMTCBsb25nIGxvbmcKCmNvbnN0IGludCBTaXplID0gMTAwMDA1NTsKY29uc3QgTEwgbW9kID0gMTAwMDAwMDAwNzsKCmludCBOLCBNLCBLOwppbnQgVGltZSA9IDA7CnZlY3RvcjxpbnQ+IEdyYXBoW1NpemVdOwppbnQgZGlzY1tTaXplXSwgbG93W1NpemVdOwppbnQgYXBbU2l6ZV07CmludCB2aXNbU2l6ZV0sIHBhcltTaXplXTsKTEwgcmVzID0gMDsKTEwgU0laRVtTaXplXTsKaW50IElEW1NpemVdOwppbnQgY29sb3IgPSAxOwppbnQgdG90YWxBUCA9IDA7Cgp2b2lkIEFQKGludCBjdXIpIHsKICAgIGRpc2NbY3VyXSA9IGxvd1tjdXJdID0gKytUaW1lOwogICAgdmlzW2N1cl0gPSAxOwogICAgaW50IGNoaWxkID0gMDsKICAgIHZlY3RvcjxpbnQ+IGFkajsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpIEdyYXBoW2N1cl0uc2l6ZSgpOyBpKyspIHsKICAgICAgICBpbnQgdiA9IEdyYXBoW2N1cl1baV07CgogICAgICAgIExMIHBydlRpbWUgPSBUaW1lOwoKICAgICAgICBpZiAodmlzW3ZdID09IDApIHsKICAgICAgICAgICAgcGFyW3ZdID0gY3VyOwogICAgICAgICAgICBjaGlsZCsrOwogICAgICAgICAgICBBUCh2KTsKICAgICAgICAgICAgYm9vbCBmID0gZmFsc2U7CiAgICAgICAgICAgIGlmIChwYXJbY3VyXSA9PSAtMSAmJiBjaGlsZCA+IDEpIHsKICAgICAgICAgICAgICAgIGFwW2N1cl0gPSAxOwogICAgICAgICAgICAgICAgZiA9IHRydWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbG93W2N1cl0gPSBtaW4obG93W3ZdLCBsb3dbY3VyXSk7CiAgICAgICAgICAgIGlmIChwYXJbY3VyXSAhPSAtMSAmJiBsb3dbdl0gPj0gZGlzY1tjdXJdKSB7CiAgICAgICAgICAgICAgICBhcFtjdXJdID0gMTsKICAgICAgICAgICAgICAgIGYgPSB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGYgPT0gdHJ1ZSl7IC8vLyBUaGVyZSBpcyBhIHN1YiBjb21wb25lbnQgd2hpY2ggaXMgY29ubmVjdGVkIHRvIHRoZSBtYWluIGdyYXBoIGJ5IGVkZ2UgY3VyLXYKICAgICAgICAgICAgICAgIGFkai5wYihUaW1lIC0gcHJ2VGltZSk7CiAgICAgICAgICAgICAgICAvLy8gVGltZSAtIHBydlRpbWUgPSB0aGUgc2l6ZSBvZiB0aGlzIHN1YiBjb21wb25lbnQKICAgICAgICAgICAgfQogICAgICAgIH0gZWxzZSBpZiAodiAhPSBwYXJbY3VyXSkgewogICAgICAgICAgICBsb3dbY3VyXSA9IG1pbihkaXNjW3ZdLCBsb3dbY3VyXSk7CiAgICAgICAgfQogICAgfQoKICAgIGlmKGFwW2N1cl0gPT0gMSkgdG90YWxBUCsrOwogICAgaWYoYWRqLnNpemUoKSA9PSAwKSByZXR1cm47CgogICAgTEwgc2l6ZU9mT3RoZXIgPSAwOwogICAgZm9yKGludCBpID0gMDtpPGFkai5zaXplKCk7aSsrKXsKICAgICAgICBzaXplT2ZPdGhlciArPSBhZGpbaV07CiAgICB9CgogICAgTEwgc2l6ZU9mQ3VyU3ViR3JhcGggPSBTSVpFW0lEW2N1cl1dIC0gc2l6ZU9mT3RoZXIgLSAxOwogICAgYWRqLnBiKHNpemVPZkN1clN1YkdyYXBoKTsKCiAgICBmb3IoaW50IGkgPSAwO2k8YWRqLnNpemUoKTtpKyspewogICAgICAgIExMIHN6ID0gYWRqW2ldOwogICAgICAgIC8vLyBObyBvZiB3YXlzIHRvIHNlbGVjdCAoUCxWKSBmb3IgY3VycmVudCBhcnRpY3VsYXRpb24gcG9pbnQKICAgICAgICBMTCBhZGQgPSBzeiAqIChTSVpFW0lEW2N1cl1dIC0gc3ogLSAxKTsKICAgICAgICBhZGQgJT0gbW9kOwogICAgICAgIHJlcyArPSBhZGQ7CiAgICAgICAgcmVzICU9IG1vZDsKICAgIH0KfQoKdm9pZCBERlMoaW50IGN1cil7CiAgICBJRFtjdXJdID0gY29sb3I7CiAgICBTSVpFW2NvbG9yXSsrOyAvLy8gU2l6ZSBvZiB0aGUgY3VycmVudCBjb21wb25lbnQKICAgIGZvcihpbnQgaSA9IDA7aTxHcmFwaFtjdXJdLnNpemUoKTtpKyspewogICAgICAgIGludCB2ID0gR3JhcGhbY3VyXVtpXTsKICAgICAgICBpZihJRFt2XSAhPSAtMSkgY29udGludWU7CiAgICAgICAgREZTKHYpOwogICAgfQp9Cgp2b2lkIHNvbHZlKCkgewogICAgQ0xSKFNJWkUsMCk7CiAgICBDTFIoSUQsLTEpOwogICAgLy8vIFVwZGF0ZSBjb2xvciBhbmQgc2l6ZSBvZiBkaWZmZXJlbnQgY29tcG9uZW50IGluIHRoZSBncmFwaC4KICAgIGZvcihpbnQgaSA9IDE7aTw9TjtpKyspewogICAgICAgIGlmKElEW2ldICE9IC0xKSBjb250aW51ZTsKICAgICAgICBERlMoaSk7CiAgICAgICAgY29sb3IrKzsKICAgIH0KICAgIGZvcihpbnQgaSA9IDA7aTxTaXplO2krKyl7CiAgICAgICAgZGlzY1tpXSA9IGxvd1tpXSA9IGFwW2ldID0gdmlzW2ldID0gMDsKICAgICAgICBwYXJbaV0gPSAtMTsKICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47IGkrKykgewogICAgICAgIGlmICh2aXNbaV0gPT0gMCkgewogICAgICAgICAgICBBUChpKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluICgpIHsKCiAgICBpbnQgdSx2OwogICAgc2NhbmYoIiVkICVkICVkIiwgJk4sICZNLCAmSyk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE07IGkrKykgewogICAgICAgIHNjYW5mKCIlZCAlZCIsICZ1LCAmdiApOwogICAgICAgIEdyYXBoW3VdLnBiKHYpOwogICAgICAgIEdyYXBoW3ZdLnBiKHUpOwogICAgfQogICAgc29sdmUoKTsKICAgIHByaW50ZigiJWxsZFxuIixyZXMpOwoKICAgIHJldHVybiAwOwp9Cg==