English · Original
Chinese · Translation
Formal · Original
_The fundamental prerequisite for justice is not to be correct, but to be strong. That's why justice is always the victor._
The Cinderswarm Bee. Koyomi knows it.
The bees, according to their nature, live in a tree. To be more specific, a complete binary tree with _n_ nodes numbered from 1 to _n_. The node numbered 1 is the root, and the parent of the _i_\-th (2 ≤ _i_ ≤ _n_) node is . Note that, however, all edges in the tree are undirected.
Koyomi adds _m_ extra undirected edges to the tree, creating more complication to trick the bees. And you're here to count the number of simple paths in the resulting graph, modulo 109 + 7. A simple path is an alternating sequence of adjacent nodes and undirected edges, which begins and ends with nodes and does not contain any node more than once. Do note that a single node is also considered a valid simple path under this definition. Please refer to the examples and notes below for instances.
## Input
The first line of input contains two space-separated integers _n_ and _m_ (1 ≤ _n_ ≤ 109, 0 ≤ _m_ ≤ 4) — the number of nodes in the tree and the number of extra edges respectively.
The following _m_ lines each contains two space-separated integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_) — describing an undirected extra edge whose endpoints are _u_ and _v_.
Note that there may be multiple edges between nodes in the resulting graph.
## Output
Output one integer — the number of simple paths in the resulting graph, modulo 109 + 7.
[samples]
## Note
In the first example, the paths are: (1); (2); (3); (1, 2); (2, 1); (1, 3); (3, 1); (2, 1, 3); (3, 1, 2). (For the sake of clarity, the edges between nodes are omitted since there are no multiple edges in this case.)
In the second example, the paths are: (1); (1, 2); (1, 2, 3); (1, 3); (1, 3, 2); and similarly for paths starting with 2 and 3. (5 × 3 = 15 paths in total.)
In the third example, the paths are: (1); (2); any undirected edge connecting the two nodes travelled in either direction. (2 + 5 × 2 = 12 paths in total.)
_正义的根本前提不是正确，而是强大。这就是为什么正义总是胜利者。_
蜜蜂群。Koyomi 知道它。
这些蜜蜂，根据其本性，生活在一棵树中。更具体地说，是一棵包含 #cf_span[n] 个节点的 #cf_span(class=[tex-font-style-underline], body=[完全二叉树])，节点编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_span[1] 的节点是根节点，而第 #cf_span[i] 个节点（#cf_span[2 ≤ i ≤ n]）的父节点是 。请注意，树中的所有边都是无向的。
Koyomi 向这棵树添加了 #cf_span[m] 条额外的无向边，以增加复杂性来迷惑蜜蜂。而你的任务是计算所得图中 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 的数量，对 #cf_span[109 + 7] 取模。一个 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 是一个由相邻节点和无向边交替组成的序列，起始和结束均为节点，且不包含任何节点超过一次。请注意，根据此定义，单个节点也被视为有效的 #cf_span(class=[tex-font-style-underline], body=[简单路径])。请参考下面的示例和注释以获取实例。
输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 109]，#cf_span[0 ≤ m ≤ 4]）——分别表示树中的节点数和额外边的数量。
接下来的 #cf_span[m] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）——描述一条无向额外边，其端点为 #cf_span[u] 和 #cf_span[v]。
请注意，所得图中节点之间可能存在多条边。
输出一个整数——所得图中 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 的数量，对 #cf_span[109 + 7] 取模。
在第一个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；#cf_span[(3)]；#cf_span[(1, 2)]；#cf_span[(2, 1)]；#cf_span[(1, 3)]；#cf_span[(3, 1)]；#cf_span[(2, 1, 3)]；#cf_span[(3, 1, 2)]。（为清晰起见，节点间的边被省略，因为此情况下不存在多重边。）
在第二个示例中，路径为：#cf_span[(1)]；#cf_span[(1, 2)]；#cf_span[(1, 2, 3)]；#cf_span[(1, 3)]；#cf_span[(1, 3, 2)]；以及类似地以 #cf_span[2] 和 #cf_span[3] 开头的路径。（总计 #cf_span[5 × 3 = 15] 条路径。）
在第三个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；以及连接这两个节点的任意无向边，无论朝哪个方向遍历。（总计 #cf_span[2 + 5 × 2 = 12] 条路径。）
## Input
输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 109]，#cf_span[0 ≤ m ≤ 4]）——分别表示树中的节点数和额外边的数量。接下来的 #cf_span[m] 行，每行包含两个用空格分隔的整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ n]，#cf_span[u ≠ v]）——描述一条无向额外边，其端点为 #cf_span[u] 和 #cf_span[v]。请注意，所得图中节点之间可能存在多条边。
## Output
输出一个整数——所得图中 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 的数量，对 #cf_span[109 + 7] 取模。
[samples]
## Note
在第一个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；#cf_span[(3)]；#cf_span[(1, 2)]；#cf_span[(2, 1)]；#cf_span[(1, 3)]；#cf_span[(3, 1)]；#cf_span[(2, 1, 3)]；#cf_span[(3, 1, 2)]。（为清晰起见，节点间的边被省略，因为此情况下不存在多重边。）
在第二个示例中，路径为：#cf_span[(1)]；#cf_span[(1, 2)]；#cf_span[(1, 2, 3)]；#cf_span[(1, 3)]；#cf_span[(1, 3, 2)]；以及类似地以 #cf_span[2] 和 #cf_span[3] 开头的路径。（总计 #cf_span[5 × 3 = 15] 条路径。）
在第三个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；以及连接这两个节点的任意无向边，无论朝哪个方向遍历。（总计 #cf_span[2 + 5 × 2 = 12] 条路径。）
**Definitions**
Let $ G = (V, E) $ be an undirected graph where:
- $ V = \{1, 2, \dots, n\} $, with $ n \in \mathbb{Z}^+ $, $ 1 \leq n \leq 10^9 $.
- The base graph is a **complete binary tree** with root at node 1, where for $ 2 \leq i \leq n $, the parent of node $ i $ is $ \lfloor i/2 \rfloor $.
- $ E_{\text{tree}} $: set of undirected edges of the complete binary tree.
- $ E_{\text{extra}} $: a multiset of $ m \in \mathbb{Z}_{\geq 0} $, $ m \leq 4 $, additional undirected edges $ \{ (u_j, v_j) \mid u_j, v_j \in V, u_j \neq v_j \} $.
- $ E = E_{\text{tree}} \cup E_{\text{extra}} $ (allowing multiple edges).
**Constraints**
1. $ 1 \leq n \leq 10^9 $
2. $ 0 \leq m \leq 4 $
3. For each extra edge $ (u, v) $, $ 1 \leq u, v \leq n $, $ u \neq v $.
**Objective**
Count the number of **simple paths** in $ G $, modulo $ 10^9 + 7 $.
A **simple path** is a finite alternating sequence $ v_1, e_1, v_2, e_2, \dots, e_{k-1}, v_k $ such that:
- Each $ v_i \in V $, each $ e_i \in E $,
- $ e_i = \{v_i, v_{i+1}\} $,
- All $ v_i $ are distinct (no repeated nodes),
- $ k \geq 1 $ (single nodes are valid paths).
Let $ P(G) $ denote the set of all simple paths in $ G $.
Compute $ |P(G)| \mod (10^9 + 7) $.
API Response (JSON)
{
"problem": {
"name": "D. The Overdosing Ubiquity",
"description": {
"content": "_The fundamental prerequisite for justice is not to be correct, but to be strong. That's why justice is always the victor._ The Cinderswarm Bee. Koyomi knows it. The bees, according to their nature,",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF869D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_The fundamental prerequisite for justice is not to be correct, but to be strong. That's why justice is always the victor._\n\nThe Cinderswarm Bee. Koyomi knows it.\n\nThe bees, according to their nature,...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_正义的根本前提不是正确，而是强大。这就是为什么正义总是胜利者。_\n\n蜜蜂群。Koyomi 知道它。\n\n这些蜜蜂，根据其本性，生活在一棵树中。更具体地说，是一棵包含 #cf_span[n] 个节点的 #cf_span(class=[tex-font-style-underline], body=[完全二叉树])，节点编号从 #cf_span[1] 到 #cf_span[n]。编号为 #cf_spa...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be an undirected graph where: \n- $ V = \\{1, 2, \\dots, n\\} $, with $ n \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 10^9 $. \n- The base graph is a **complete binary tree**...",
"is_translate": false,
"language": "Formal"
}
]
}