C0849 [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$

样例输入 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