分数: 100 点
问题陈述
有 N 漂浮在林戈海的岛屿,以及 M 旅行社在这些岛屿之间运营船只。为了方便起见,我们将这些岛屿称为岛屿 1, 2, …, N, 并致电这些代理 1, 2, …, M.
林戈海的海流每天都在发生显着变化。根据当天的海况,代理 i (1 ≤ i ≤ M) 从岛上运营船舶 a_i to b_i,或岛屿 b_i to a_i,但不能同时两者。假设每个智能体的船只方向都是以相等的概率独立选择的。
现在,高桥在岛上 1,并且 Hikuhashi 在岛上 2。让 P 是高桥和 Hikuhashi 可以在一天内乘坐由该公司运营的船只前往同一岛屿的概率 M 代理,忽略船舶行驶时间等因素。然后, P × 2^M 是一个整数。 P × 2^M 模数 10^9 + 7.
约束
- 2 ≤ N ≤ 15
- 1 ≤ M ≤ N(N-1)/2
- 1 ≤ a_i < b_i ≤ N
- 所有对 (a_i, b_i) 是不同的。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 : a_M b_M
输出
打印该值 P × 2^M 模数 10^9 + 7.
示例输入 1
4 3 1 3 2 3 3 4
示例输出 1
6
的 树的 2^M = 8 上述场景发生的概率相同,高桥和日桥可以在同一个岛上相遇 其中 6 。因此, P = 6/2^M 和 P × 2^M = 6.
示例输入 2
5 5 1 3 2 4 3 4 3 5 4 5
示例输出 2
18
示例输入 3
6 6 1 2 2 3 3 4 4 5 5 6 1 6
示例输出 3
64