正义的根本前提不是正确,而是坚强。所以正义永远是胜利者。
煤渣蜂。久美知道这一点。
蜜蜂根据其本性生活在树上。更具体地说,是一棵有 n 个节点的完全二叉树,编号从 1 到 n。编号为 1 的节点是根节点,第 i (2 ≤ i ≤ n) 个节点的父节点是 $$\left\lfloor \frac { i } { 2 } \right\rfloor$$。但请注意,树中的所有边都是无向的。
Koyomi 在树中添加了 m 个额外的无向边,从而使欺骗蜜蜂变得更加复杂。您在这里计算结果图中简单路径的数量,以 109 + 7 为模。简单路径是相邻节点和无向边的交替序列,它以节点开始和结束,并且不包含任何节点超过一次。请注意,在此定义下,单个节点也被视为有效的简单路径。请参考下面的示例和注释。
输入
输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 109, 0 ≤ m ≤ 4) — 分别是树中的节点数和额外边的数量。
接下来的 m 行每行包含两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) — 描述一条无向额外边,其端点为 u 和 v。
请注意,结果图中的节点之间可能存在多条边。
输出
输出一个整数 — 结果图中简单路径的数量,模 109 + 7。
示例
输入 #1
3 0
输出 #1
9
输入 #2
3 1 2 3
输出 #2
15
输入 #3
2 4 1 2 2 1 1 2 2 1
输出 #3
12
注意
在第一个示例中,路径为: (1); (2); (3); (1, 2); (2, 1); (1, 3); (3, 1); (2,1,3); (3,1,2)。 (为了清楚起见,省略了节点之间的边,因为在这种情况下没有多条边。)
在第二个示例中,路径为: (1); (1, 2); (1,2,3); (1, 3); (1,3,2);对于以 2 和 3 开头的路径也类似。(5 × 3 = 总共 15 条路径。)
在第三个示例中,路径是: (1); (2);连接两个节点的任何无向边沿任一方向行进。 (2 + 5 × 2 = 总共 12 条路径。)