← 返回题目列表

AtCoder · relay2_i

I. 很高兴认识你

中文机器翻译题面 查看原题

分数: 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
36cba65088d9b1224a6ce9665aa44048.png

的 树的 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