题目描述

りんご海に $N$ 個の島が浮かんでおり、$M$ 社の業者がこれらの島を結ぶ船便を運行しています。便宜上、これらの島を島 $1,$ $2,$ $…,$ $N$ と呼び、これらの業者を業者 $1$, $2$, $…,$ $M$ と呼びます。

りんご海の海流は毎日大きく変わります。業者 $i$ $(1\ <\ =\ i\ <\ =\ M)$ は、その日の海の状況に応じて、島 $a_i$ から $b_i$ への便または島 $b_i$ から $a_i$ への便のどちらか一方のみを運行します。どちらの方向の便が運行されるかは、それぞれの業者について独立に、等確率で決定されるものとします。

いま、島 $1$ に高橋くんが、島 $2$ に低橋くんがいます。$M$ 社の業者による船便を用いて、高橋くんと低橋くんがその日のうちに同じ島に移動することができる確率を $P$ とします。ただし、船の所要時間などは無視します。このとき、$P\ ×\ 2^M$ は整数となります。$P\ ×\ 2^M$ を $10^9\ +\ 7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $:$ $a_M$ $b_M$

输出格式

値 $P\ ×\ 2^M$ を $10^9\ +\ 7$ で割ったあまりを出力せよ。

题目大意

给定一张无向图，需要给每一条边定向，求1号点和2号点能到达相同点的方案数。

4 3
1 3
2 3
3 4

6

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

18

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

64

提示

制約

• $2\ <\ =\ N\ <\ =\ 15$
• $1\ <\ =\ M\ <\ =\ N(N-1)/2$
• $1\ <\ =\ a_i\ <\ b_i\ <\ =\ N$
• 組 $(a_i,\ b_i)$ はすべて異なる。

Sample Explanation 1

 上図に示した $2^M\ =\ 8$ 通りの状況が等確率で発生し、そのうち高橋くんと低橋くんが同じ島で出会える状況は $6$ 通りです。したがって、$P\ =\ 6/2^M,$ $P\ ×\ 2^M\ =\ 6$ となります。