配点 : $100$ 点

問題文

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

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

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

制約

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

入力

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

$N$ $M$

$a_1$ $b_1$

$:$

$a_M$ $b_M$

出力

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

4 3
1 3
2 3
3 4

6

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