AT_relay2_i Nice to Meet You

在“りんご海”上漂浮着 $N$ 个岛屿，有 $M$ 家公司经营这些岛屿之间的船运。为了方便，设这些岛屿分别编号为 $1, 2, \ldots, N$，这些公司编号为 $1, 2, \ldots, M$。 “りんご海”的洋流每天都会发生巨大变化。第 $i$ 家公司（$1 \leq i \leq M$）每天会根据当天的海况，仅经营从岛 $a_i$ 到岛 $b_i$ 的船，或仅经营从 $b_i$ 到 $a_i$ 的船这两种情况之一。对于每家公司，决定经营哪一个方向是完全独立并且等概率的。 现在，高桥君在岛 $1$，低桥君在岛 $2$。请你计算，当天两人能否通过这些公司的船，在一天之内相遇在同一个岛上的概率 $P$。忽略船只所需的时间等其他限制。在这种情况下，$P \times 2^M$ 一定是整数。请输出 $P \times 2^M$ 对 $10^9+7$ 取模的结果。

输入通过标准输入给出，格式如下： > $N$ $M$ > $a_1$ $b_1$ > $\vdots$ > $a_M$ $b_M$

输出 $P \times 2^M$ 对 $10^9+7$ 取模的结果。

## 限制条件 - $2 \leq N \leq 15$ - $1 \leq M \leq \frac{N(N-1)}{2}$ - $1 \leq a_i < b_i \leq N$ - 每一组 $(a_i, b_i)$ 均不相同。 ## 样例说明1  如上图所示，所有 $2^M = 8$ 种可能的情况等概率出现，其中能够让高桥君和低桥君相遇的情况有 $6$ 种。因此 $P = 6 / 2^M$，$P \times 2^M = 6$。 由 ChatGPT 5 翻译