爱丽丝最近发现她家附近长着一些仙人掌!几个月后,仙人掌越来越多,很快就把路堵住了。所以爱丽丝想清除它们。
仙人掌是一个连通的无向图。该图的任何一条边都位于一个以上的简单循环上。我们将图 $$$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$$$ 的方差,如果图中的所有节点都有概率 $$$\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$$$ 的整数。换句话说,找到这样一个整数 $$$x$$$ 使得 $$$0 \le x < M$$$ 且 $$$x \cdot q \equiv p \pmod{M}$$$。
输入
第一行包含两个整数 $$$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$$$ 之间有一条边。
保证图中不存在环和重边,并且给定的图是仙人掌。
输出
打印一个整数 - 删除一组节点后,剩余图中的连通分量数量的方差,使得每个节点都有 $$$\frac{1}{2}$$$ 被删除的概率,并且所有这些事件都是独立的。该值应通过模 $$$10^9+7$$$ 找到。
示例
输入 #1
3 3 1 2 2 3 1 3
输出 #1
984375007
输入 #2
5 6 1 2 2 3 1 3 3 4 4 5 3 5
输出 #2
250000002
注意
在第一个示例中,答案是 $$$\frac{7}{64}$$$。如果删除所有节点,则 $$$X$$$ 的值等于 $$$0$$$,否则等于 $$$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}$$$。