CF1236F.Alice and the Cactus

Alice recently found some cactuses growing near her house! After several months, more and more cactuses appeared and soon they blocked the road. So Alice wants to clear them.

A cactus is a connected undirected graph. No edge of this graph lies on more than one simple cycle. Let's call a sequence of different nodes of the graph $x_1, x_2, \ldots, x_k$ a simple cycle, if $k \geq 3$ and all pairs of nodes $x_1$ and $x_2$, $x_2$ and $x_3$, $\ldots$, $x_{k-1}$ and $x_k$, $x_k$ and $x_1$ are connected with edges. Edges $(x_1, x_2)$, $(x_2, x_3)$, $\ldots$, $(x_{k-1}, x_k)$, $(x_k, x_1)$ lies on this simple cycle.

There are so many cactuses, so it seems hard to destroy them. But Alice has magic. When she uses the magic, every node of the cactus will be removed independently with the probability $\frac{1}{2}$. When a node is removed, the edges connected to it are also removed.

Now Alice wants to test her magic. She has picked a cactus with $n$ nodes and $m$ edges. Let $X[S]$ (where $S$ is a subset of the removed nodes) be the number of connected components in the remaining graph after removing nodes of set $S$. Before she uses magic, she wants to know the variance of random variable $X$, if all nodes of the graph have probability $\frac{1}{2}$ to be removed and all $n$ of these events are independent. By the definition the variance is equal to $E[(X - E[X])^2]$, where $E[X]$ is the expected value of $X$. Help her and calculate this value by modulo $10^9+7$.

Formally, let $M = 10^9 + 7$ (a prime number). It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, find such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

爱丽丝最近在她家附近发现了一些仙人掌！几个月后，越来越多的仙人掌冒了出来，很快便堵塞了道路。因此，爱丽丝想要清除它们。

仙人掌图 是一个连通的无向图，其中任意一条边至多属于一个简单环。我们称图中一列互不相同的节点 $x_1, x_2, \ldots, x_k$ 为一个简单环，当且仅当 $k \geq 3$，且所有相邻节点对 $x_1$ 与 $x_2$、$x_2$ 与 $x_3$、$\ldots$、$x_{k-1}$ 与 $x_k$、$x_k$ 与 $x_1$ 均由边相连。这些边 $(x_1, x_2)$、$(x_2, x_3)$、$\ldots$、$(x_{k-1}, x_k)$、$(x_k, x_1)$ 均属于该简单环。

仙人掌数量众多，似乎难以全部摧毁。但爱丽丝拥有魔法：当她施放魔法时，仙人掌图中的每个节点将独立地以概率 $\frac{1}{2}$ 被移除；一旦某个节点被移除，所有与其相连的边也将一并被移除。

现在爱丽丝想测试她的魔法。她已选定一棵含 $n$ 个节点和 $m$ 条边的仙人掌图。令 $X[S]$（其中 $S$ 是被移除节点的子集）表示从原图中移除集合 $S$ 中所有节点后，剩余图的连通分量数目。在施放魔法前，她希望知道随机变量 $X$ 的方差（variance）——即假设图中每个节点均以概率 $\frac{1}{2}$ 被移除，且这 $n$ 个事件相互独立时的方差。根据定义，方差为 $E[(X - E[X])^2]$，其中 $E[X]$ 表示 $X$ 的期望值。请帮助她计算该值，并对 $10^9+7$ 取模。

形式化地，令 $M = 10^9 + 7$（一个质数）。可以证明，答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，求满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The first line contains two integers $n$ and $m$, separated by space ($1 \leq n \leq 5 \cdot 10^5, n - 1 \leq m \leq 5 \cdot 10^5$) — the number of nodes and edges in the cactus.

The following $m$ lines contain two numbers $u$ and $v$ each, separated by space ($1 \leq u, v \leq n, u \neq v$) meaning that there is an edge between the nodes $u$ and $v$.

It is guaranteed that there are no loops and multiple edges in the graph and the given graph is cactus.

第一行包含两个整数 $n$ 和 $m$，以空格分隔（$1 \leq n \leq 5 \cdot 10^5$，$n - 1 \leq m \leq 5 \cdot 10^5$）——分别表示仙人掌图中的节点数和边数。

接下来的 $m$ 行每行包含两个数字 $u$ 和 $v$，以空格分隔（$1 \leq u, v \leq n$，$u \neq v$），表示节点 $u$ 与节点 $v$ 之间存在一条边。

保证图中不存在自环和重边，且给定的图是一棵仙人掌图。

Print one integer — the variance of the number of connected components in the remaining graph, after removing a set of nodes such that each node has probability $\frac{1}{2}$ to be removed and all these events are independent. This value should be found by modulo $10^9+7$.

输出一个整数——在以概率 $\frac{1}{2}$ 独立地移除每个节点后，剩余图中连通分量数量的方差。该值需对 $10^9+7$ 取模。

In the first sample, the answer is $\frac{7}{64}$. If all nodes are removed the value of $X$ is equal to $0$, otherwise, it is equal to $1$. So, the expected value of $X$ is equal to $0\times\frac{1}{8}+1\times\frac{7}{8}=\frac{7}{8}$. So, the variance of $X$ is equal to $(0 - \frac{7}{8})^2\times\frac{1}{8}+(1-\frac{7}{8})^2\times\frac{7}{8} = (\frac{7}{8})^2\times\frac{1}{8}+(\frac{1}{8})^2\times\frac{7}{8} = \frac{7}{64}$.

In the second sample, the answer is $\frac{1}{4}$.

在第一个样例中，答案为 $\frac{7}{64}$。若所有节点均被移除，则 $X$ 的值为 $0$；否则，$X$ 的值为 $1$。因此，$X$ 的期望值为 $0\times\frac{1}{8}+1\times\frac{7}{8}=\frac{7}{8}$。于是，$X$ 的方差为 $(0 - \frac{7}{8})^2\times\frac{1}{8}+(1-\frac{7}{8})^2\times\frac{7}{8} = (\frac{7}{8})^2\times\frac{1}{8}+(\frac{1}{8})^2\times\frac{7}{8} = \frac{7}{64}$。

在第二个样例中，答案为 $\frac{1}{4}$。