#2547. 「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（防御子网络连通）的前提下，选取的边数最小，即 $|H(S)|$ 最小。

$H(S)$ 是点集 $S$ 在图 $G$ 生成的斯坦纳树 (Steiner Tree)，而 $|H(S)|$ 则是启动防御子网络的最小代价。考虑到外星母舰随机攻击的方式，JYY 希望你计算启动防御子网络代价的期望：

$$\frac{1}{2^{|V|}}\sum_{S \subseteq V}|H(S)|$$

输入格式

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

输出格式

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

样例

样例 1

输入

3 2
1 2
2 3

输出

750000006

样例 2

输入

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

输出

468750006

样例解释

样例 1 是一条链，包含以下情况：

• $S \in \{\{\}, \{1\}, \{2\}, \{3\}\}, |H(S)| = 0$;
• $S \in \{\{1, 2\}, \{2, 3\}\}, |H(S)| = 1$;
• $S \in \{\{1, 3\}, \{1, 2, 3\}\}, |H(S)| = 2$。

因此 $P/Q = 3/4$， $P \cdot Q^{-1} = 750,000,006 \pmod{1,000,000,007}$。

样例 2 中 $\sum_{S \subseteq V}|H(S)| = 174$，因此 $P/Q = 87/32$， $P \cdot Q^{-1} = 468,750,006 \pmod{1,000,000,007}$。

数据范围与提示

• 对于 $20\%$ 的数据，有 $1 \le n \le 8$。
• 对于 $40\%$ 的数据，有 $1 \le n \le 20$。
• 对于 $100\%$ 的数据，有 $1 \le n \le 200$。