期望好题。
首先拆方差：
因此我们只需 (E(x^2)) 和 (E(x)) 即可求解出答案。
考虑 (x) 是什么东西。直接从连通块个数的角度下手异常棘手。不过注意到原图是一个仙人掌，因此假设点数、边数、环数分别为 (a,b,c)，那么连通块个数 (x=a-b+c)，这可以看作原本有 (a) 个连通块，每加入一条边会少一个连通块，但有 (c) 次加边时成环，连通块个数不变。
因此 (E(x^2)=E((a-b+c)^2)=E(a^2)+E(b^2)+E(c^2)-2E(ab)+2E(ac)-2E(bc))，(E(x)=E(a)-E(b)+E(c))。
考虑对这九个东西分别计算：
1. (E(a))
显然 (E(a)=dfrac{n}{2})
2. (E(b))
显然 (E(b)=dfrac{m}{4})，因为每条边有 (dfrac{1}{4}) 的概率存在。
3. (E(c))
假设原仙人掌中第 (i) 个环点数为 (C_i)，那么显然第 (i) 个环被保留的概率就是 (p_i=dfrac{1}{2^{C_i}})
期望环数 (=sumlimits_{i=1}^cp_i)，其中 (c) 为原仙人掌中环数。
4. (E(a^2))
根据期望的线性性 (E(a^2)) 等于每对点同时存在的概率。
考虑对于两个点 (i,j)：
- 如果 (i=j)，那它们同时存在的概率为 (dfrac{1}{2})
- 否则它们同时存在的概率为 (dfrac{1}{4})
化简一下可得 (E(a^2)=dfrac{n(n+1)}{4})
5. (E(b^2))
根据期望的线性性 (E(b^2)) 等于每对边同时存在的概率。
考虑两条边 (i,j)：
- 如果 (i=j)，那它们同时存在的概率为 (dfrac{1}{4})
- 如果 (i,j) 两条边恰好存在一个公共端点，那么它们同时存在的概率为 (dfrac{1}{8})
- 否则它们同时存在的概率为 (dfrac{1}{16})
对于第一种情况贡献就是 (E(b))，直接加上，对于第二种情况就枚举公共点，这样可以算得有多少对边符合第二种情况，剩余的边肯定都属于第三种情况了。
6. (E(c^2))
根据期望的线性性 (E(c^2)) 等于每对环同时存在的概率。
考虑两个环 (i,j)，由于原图是仙人掌两个不同的环最多只有一个公共点：
- 如果 (i=j)，那它们同时存在的概率为 (p_i)
- 如果 (i,j) 两个环恰好存在一个公共点，那它们同时存在的概率为 (p_i·p_j·2)
- 否则它们同时存在的概率为 (p_i·p_j)
和 (E(b^2)) 的求法类似，第一种情况的贡献就是 (E(c))，对于二三两种情况我们先额外将所有 (i e j) 的 (p_i·p_j) 加入答案，再额外枚举所有符合第二类限制的两个环 (i,j)，再将它们的 (p_i·p_j) 累加入答案。具体求法也是枚举公共点然后扫一遍，并维护当前扫过的所有环的 (p_i) 之和即可算出贡献。
7. (E(ab))
根据期望的线性性 (E(ab)) 等于每个点与每条边同时存在的概率之和。
考虑一个点 (a) 和一条边 (e)：
- 如果 (a) 是 (e) 的一个端点，那么它们同时存在的概率为 (dfrac{1}{4})
- 否则它们同时存在的概率为 (dfrac{1}{8})
枚举每个点，然后预处理每个点的度即可算出有多少条边符合第一种情况，有多少条边符合第二种情况。
8. (E(ac))
根据期望的线性性 (E(ac)) 等于每个点与每个环同时存在的概率之和。
考虑一个点 (a) 和一个环 (c)：
- 如果 (a) 在 (c) 上，那它们同时存在的概率为 (p_c)
- 否则它们同时存在的概率为 (dfrac{1}{2}p_c)
还是按照套路枚举环 (c)，预处理每个环上的点数即可知道有多少个点符合第一种情况，有多少个点符合第二种情况。
9. (E(bc))
根据期望的线性性 (E(bc)) 等于每条边与每个环同时存在的概率之和。
考虑一条边 (e) 和一个环 (c)：
- 如果 (e) 的两个端点都在 (c) 上，那它们同时存在的概率为 (p_c)
- 如果 (e) 的一个端点在 (c) 上，那它们同时存在的概率为 (dfrac{1}{2}p_c)
- 如果 (e) 的两个端点都不在 (c) 上，那它们同时存在的概率为 (dfrac{1}{4}p_c)
对于第一种情况还是通过预处理每个环上的点数即可快速算出，第二种情况符合条件的边数即为环上每个点的度数减 (2) 之和，剩余的边都是第三种情况。
时间复杂度 (mathcal O(n+m))。
const int MAXN=5e5;
const int MOD=1e9+7;
const int INV2=MOD+1>>1;
const int INV4=MOD+1>>2;
const int INV8=MOD+1>>3;
const int INV16=((MOD+9>>4)-INV2+MOD)%MOD;
int n,m,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int dfn[MAXN+5],fa[MAXN+5],tim=0,ipw2[MAXN+5];
vector<int> cyc[MAXN+5],bel[MAXN+5];
int cycnt=0,P[MAXN+5],deg[MAXN+5];
void dfs(int x){
dfn[x]=++tim;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];
if(!dfn[y]) fa[y]=x,dfs(y);
else if(dfn[y]<dfn[x]&&y!=fa[x]){
cycnt++;
for(int i=x;i^y;i=fa[i]) cyc[cycnt].pb(i),bel[i].pb(cycnt);
cyc[cycnt].pb(y);bel[y].pb(cycnt);
}
}
}
int Ea(){return 1ll*n*INV2%MOD;}
int Eb(){return 1ll*m*INV4%MOD;}
int Ec(){int sum=0;for(int i=1;i<=cycnt;i++) sum=(sum+P[i])%MOD;return sum;}
int Ex(){return (0ll+Ea()-Eb()+Ec()+MOD)%MOD;}
int Eaa(){return 1ll*n*(n+1)%MOD*INV4%MOD;}
int Ebb(){
ll tot=1ll*m*(m-1);int res=1ll*m*INV4%MOD;
for(int i=1;i<=n;i++){
tot-=1ll*deg[i]*(deg[i]-1);
res=(res+1ll*deg[i]*(deg[i]-1)%MOD*INV8)%MOD;
} res=(res+1ll*tot%MOD*INV16)%MOD;
return res;
}
int Ecc(){
ll tot=1ll*cycnt*(cycnt-1);int res=Ec(),sum=0;
for(int i=1;i<=cycnt;i++) res=(res+2ll*sum*P[i])%MOD,sum=(sum+P[i])%MOD;
for(int i=1;i<=n;i++){
int ssum=0;
for(int j:bel[i]) res=(res+2ll*ssum*P[j])%MOD,ssum=(ssum+P[j])%MOD;
} return res;
}
int Eab(){
int res=0;
for(int i=1;i<=n;i++) res=(res+1ll*INV4*deg[i]+1ll*INV8*(m-deg[i]))%MOD;
return res;
}
int Eac(){
int res=0,sm=Ec();
for(int i=1;i<=n;i++){
int ssum=0;
for(int j:bel[i]) ssum=(ssum+P[j])%MOD;
res=(0ll+res+ssum+1ll*INV2*(sm-ssum+MOD))%MOD;
} return res;
}
int Ebc(){
int res=0;
for(int i=1;i<=cycnt;i++) res=(res+1ll*P[i]*cyc[i].size())%MOD;
for(int i=1;i<=cycnt;i++){
int sum_ed=0,rst;
for(int j:cyc[i]) sum_ed+=deg[j]-2;
rst=m-cyc[i].size()-sum_ed;
res=(0ll+res+1ll*P[i]*INV2%MOD*sum_ed+1ll*P[i]*INV4%MOD*rst)%MOD;
} return res;
}
int sqr(int x){return 1ll*x*x%MOD;}
int main(){
scanf("%d%d",&n,&m);
for(int i=(ipw2[0]=1);i<=n;i++) ipw2[i]=1ll*ipw2[i-1]*INV2%MOD;
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);adde(u,v);adde(v,u);
deg[u]++;deg[v]++;
} dfs(1);for(int i=1;i<=cycnt;i++) P[i]=ipw2[cyc[i].size()];
// printf("%d
",Ec());
printf("%d
",((0ll+Eaa()+Ebb()+Ecc()-2ll*Eab()-2ll*Ebc()+2ll*Eac()-sqr(Ex()))%MOD+MOD)%MOD);
return 0;
}