{"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, 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.\n\nKoyomi 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.\n\n## Input\n\nThe 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.\n\nThe 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_.\n\nNote that there may be multiple edges between nodes in the resulting graph.\n\n## Output\n\nOutput one integer — the number of simple paths in the resulting graph, modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn 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.)\n\nIn 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.)\n\nIn 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.)","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_span[1] 的节点是根节点，而第 #cf_span[i] 个节点（#cf_span[2 ≤ i ≤ n]）的父节点是 。请注意，树中的所有边都是无向的。\n\nKoyomi 向这棵树添加了 #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=[简单路径])。请参考下面的示例和注释以获取实例。\n\n输入的第一行包含两个用空格分隔的整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 109]，#cf_span[0 ≤ m ≤ 4]）——分别表示树中的节点数和额外边的数量。\n\n接下来的 #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]。\n\n请注意，所得图中节点之间可能存在多条边。\n\n输出一个整数——所得图中 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 的数量，对 #cf_span[109 + 7] 取模。\n\n在第一个示例中，路径为：#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)]。（为清晰起见，节点间的边被省略，因为此情况下不存在多重边。）\n\n在第二个示例中，路径为：#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] 条路径。）\n\n在第三个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；以及连接这两个节点的任意无向边，无论朝哪个方向遍历。（总计 #cf_span[2 + 5 × 2 = 12] 条路径。）\n\n## Input\n\n输入的第一行包含两个用空格分隔的整数 #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]。请注意，所得图中节点之间可能存在多条边。\n\n## Output\n\n输出一个整数——所得图中 #cf_span(class=[tex-font-style-underline], body=[简单路径]) 的数量，对 #cf_span[109 + 7] 取模。\n\n[samples]\n\n## Note\n\n在第一个示例中，路径为：#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)]。（为清晰起见，节点间的边被省略，因为此情况下不存在多重边。）\n\n在第二个示例中，路径为：#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] 条路径。）\n\n在第三个示例中，路径为：#cf_span[(1)]；#cf_span[(2)]；以及连接这两个节点的任意无向边，无论朝哪个方向遍历。（总计 #cf_span[2 + 5 × 2 = 12] 条路径。）","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** with root at node 1, where for $ 2 \\leq i \\leq n $, the parent of node $ i $ is $ \\lfloor i/2 \\rfloor $.  \n- $ E_{\\text{tree}} $: set of undirected edges of the complete binary tree.  \n- $ 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 \\} $.  \n- $ E = E_{\\text{tree}} \\cup E_{\\text{extra}} $ (allowing multiple edges).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^9 $  \n2. $ 0 \\leq m \\leq 4 $  \n3. For each extra edge $ (u, v) $, $ 1 \\leq u, v \\leq n $, $ u \\neq v $.  \n\n**Objective**  \nCount the number of **simple paths** in $ G $, modulo $ 10^9 + 7 $.  \n\nA **simple path** is a finite alternating sequence $ v_1, e_1, v_2, e_2, \\dots, e_{k-1}, v_k $ such that:  \n- Each $ v_i \\in V $, each $ e_i \\in E $,  \n- $ e_i = \\{v_i, v_{i+1}\\} $,  \n- All $ v_i $ are distinct (no repeated nodes),  \n- $ k \\geq 1 $ (single nodes are valid paths).  \n\nLet $ P(G) $ denote the set of all simple paths in $ G $.  \nCompute $ |P(G)| \\mod (10^9 + 7) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF869D","tags":["brute force","dfs and similar","graphs"],"sample_group":[["3 0","9"],["3 1\n2 3","15"],["2 4\n1 2\n2 1\n1 2\n2 1","12"]],"created_at":"2026-03-03 11:00:39"}}