[JSOI2018]防御网络

题目描述

虽然成功得到了外星人的进攻计划,但 ``JYY`` 意外地发现,外星母舰对地球的攻击竟然是随机的!必须尽快在地球上部署防御网络,抵御外星人母舰的攻击。 地球上的防御网络由节点和节点之间的能量连接组成,防御网络可以看成是一个 $n$ 个点、 $m$ 条边的简单无向图 $G(V,E)$ ,每个防御节点对应 $V$ 中的一个节点、每个能量连接对应 $E$ 中的一条边。此外,在防御网络修建时考虑到能量传输效率,防御网络 $G$ 中**每个节点至多只包含在一个简单环中**。 外星母舰的攻击是随机的,每次攻击开始后, ``JYY`` 都会本次攻击的情况选择一些防御节点 $S\subseteq V$ ,并且用能量连接将这些防御节点连通,从而启动一个防御子网络。换言之, ``JYY`` 会选择 $G$ 中边集的一个子集 $H(S)\subseteq E$ ,它满足: 1. (防御子网络**连通**) 如果我们建立新图 $G'(V,H(S))$ ,即用 $H(S)$ 中的边连接 $G$ 中的节点,则对于任意选择的防御节点 $x,y\in S$ ,它们在 $G'$​​ 中都连通。 2. (防御子网络**最小**) 在满足条件 1 (防御子网络连通)的前提,选取的边数最小,即 $\vert H(S)\vert$ 最小。 $H(S)$ 是点集 $S$ 在图 $G$ 生成的斯坦纳树 (Steiner Tree) ,而 $\vert H(S)\vert$ 则是启动防御子网络的最小代价。考虑到外星母舰随机攻击的方式, ``JYY`` 希望你计算启动防御子网络代价的**期望**: $$\frac{1}{2^{\vert V\vert}}\sum_{S\subseteq V}\vert H(S)\vert$$

输入输出格式

输入格式


输入第一行两个整数 $n,m$ ,分别表示图中的节点数和边数。 接下来 $m$ 行,每行两个整数 $u,v(1\le u,v\le n)$ ,表示图中的一条边。输入保证没有自环和重边,并且满足每个节点至多包含在一个简单环中。

输出格式


输出一行,表示启动防御子网络的期望。 假设期望写成最简分式 $P/Q$ 的形式, 则输出 $P⋅Q^{-1} \text{mod 1,000,000,007}$ 的余数,其中 $Q^{-1}$​​ 为唯一的满足 $Q⋅Q^{-1} ≡ \text{1 (mod 1,000,000,007)}$ 的整数。

输入输出样例

输入样例 #1

3 2
1 2
2 3

输出样例 #1

750000006

输入样例 #2

6 6
1 2
2 3
3 1
1 4
2 5
3 6

输出样例 #2

468750006

说明

**样例解释** 样例输入 1 是一条链,包含以下情况: 1. $\{\}, \{1\}, \{2\}, \{3\},\vert H(S)\vert = 0$ ; 2. $\{1, 2\}, \{2, 3\}, \vert H(S)\vert = 1$ ; 3. $\{1, 3\}, \{1, 2, 3\}, \vert H(S)\vert = 2$ 。 因此 $P/Q=3/4$ , $P\cdot Q^{-1} = 750,000,006$ 。 样例输入 2 中 $\sum_{S\subseteq V}\vert H(S)\vert = 174$ ,因此 $P/Q=87/32$ , $P⋅Q^{-1}=468,750,006 \text{ mod 1,000,000,007}$ 。 **数据范围** 对于 $20\%$ 的数据,有 $1\le n\le 8$ 。 对于 $40\%$ 的数据,有 $1\le n\le 20$ 。 对于 $100\%$ 的数据,有 $1\le n\le 200$ 。