CF869D The Overdosing Ubiquity

实现正义的根本前提并不是“正确”，而是“强大”。因此正义总是胜者。 Cinderswarm Bee。Koyomi 知道这一点。 蜜蜂按照它们的习性，居住在一棵树上。更具体地说，是一棵节点编号为 $1$ 到 $n$ 的完全二叉树。编号为 $1$ 的节点是树根，第 $i$ 个节点（$2 \le i \le n$）的父节点为 $\left\lfloor \frac{i}{2} \right\rfloor$。注意，树上所有边都是无向的。 Koyomi 给这棵树添加了 $m$ 条额外的无向边，进一步增添了蜜蜂的迷惑。现在你的任务是计算在加边后得到的图中有多少条简单路径，对 $10^9+7$ 取模。简单路径是顶点和无向边交替组成的序列，以顶点开始和结束，且每个顶点最多经过一次。需要注意，单个节点也被认为是一条合法的简单路径。请参见下方示例和说明。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \le n \le 10^9$，$0 \le m \le 4$）——树的节点数和额外添加的边数。 接下来的 $m$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \le u,v \le n$，$u \ne v$），表示一条无向的额外边，其端点为 $u$ 和 $v$。 注意，最终的图中同一对节点之间可能有多条边。

输出一个整数，表示该图中简单路径的数量，对 $10^9+7$ 取模。

在第一个样例中，所有路径如下：$(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\times3=15$ 条路径。） 在第三个样例中，所有路径如下：$(1)$；$(2)$；任意一条连接两节点的无向边可双向行走。（$2+5\times2=12$ 条路径。） 由 ChatGPT 5 翻译