{"problem":{"name":"E. Andryusha and Nervous Barriers","description":{"content":"Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has _w_ columns numbered from 1 to _w_ from left to right, and _h_ rows","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF781E"},"statements":[{"statement_type":"Markdown","content":"Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has _w_ columns numbered from 1 to _w_ from left to right, and _h_ rows numbered from 1 to _h_ from the bottom to the top.\n\nFurther, there are barriers in some of board rows. There are _n_ barriers in total, and _i_\\-th of them occupied the cells _l__i_ through _r__i_ of the row _u__i_. Andryusha recollects well that no two barriers share the same row. Furthermore, no row is completely occupied with a barrier, that is, at least one cell in each row is free.\n\nThe player can throw a marble to any column of the machine from above. A marble falls downwards until it encounters a barrier, or falls through the bottom of the board. A marble disappears once it encounters a barrier but is replaced by two more marbles immediately to the left and to the right of the same barrier. In a situation when the barrier is at an edge of the board, both marbles appear next to the barrier at the side opposite to the edge. More than one marble can occupy the same place of the board, without obstructing each other's movement. Ultimately, all marbles are bound to fall from the bottom of the machine.\n\n Examples of marble-barrier interaction.Peculiarly, sometimes marbles can go through barriers as if they were free cells. That is so because the barriers are in fact alive, and frightened when a marble was coming at them from a very high altitude. More specifically, if a marble falls towards the barrier _i_ from relative height more than _s__i_ (that is, it started its fall strictly higher than _u__i_ + _s__i_), then the barrier evades the marble. If a marble is thrown from the top of the board, it is considered to appear at height (_h_ + 1).\n\nAndryusha remembers to have thrown a marble once in each of the columns. Help him find the total number of marbles that came down at the bottom of the machine. Since the answer may be large, print it modulo 109 + 7.\n\n## Input\n\nThe first line contains three integers _h_, _w_, and _n_ (1 ≤ _h_ ≤ 109, 2 ≤ _w_ ≤ 105, 0 ≤ _n_ ≤ 105) — the number of rows, columns, and barriers in the machine respectively.\n\nNext _n_ lines describe barriers. _i_\\-th of these lines containts four integers _u__i_, _l__i_, _r__i_, and _s__i_ (1 ≤ _u__i_ ≤ _h_, 1 ≤ _l__i_ ≤ _r__i_ ≤ _w_, 1 ≤ _s__i_ ≤ 109) — row index, leftmost and rightmost column index of _i_\\-th barrier, and largest relative fall height such that the barrier does not evade a falling marble. It is guaranteed that each row has at least one free cell, and that all _u__i_ are distinct.\n\n## Output\n\nPrint one integer — the answer to the problem modulo 109 + 7.\n\n[samples]\n\n## Note\n\nIn the first sample case, there is a single barrier: if one throws a marble in the second or the third column, two marbles come out, otherwise there is only one. The total answer is 7.\n\nIn the second sample case, the numbers of resulting marbles are 2, 2, 4, 4, 4 in order of indexing columns with the initial marble.\n\nIn the third sample case, the numbers of resulting marbles are 1, 1, 4, 4, 4. Note that the first barrier evades the marbles falling from the top of the board, but does not evade the marbles falling from the second barrier.\n\nIn the fourth sample case, the numbers of resulting marbles are 2, 2, 6, 6, 6, 6, 6, 6, 6, 1, 2, 1, 1, 1, 1. The picture below shows the case when a marble is thrown into the seventh column.\n\n The result of throwing a marble into the seventh column.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Andryusha 找到了一台令人困惑的投币游戏机。这台机器是一个垂直排列的板子，被划分为若干方格。板子有 #cf_span[w] 列，从左到右编号为 #cf_span[1] 到 #cf_span[w]，以及 #cf_span[h] 行，从下到上编号为 #cf_span[1] 到 #cf_span[h]。\\n\\n此外，某些行中存在障碍物。总共有 #cf_span[n] 个障碍物，第 #cf_span[i] 个障碍物占据第 #cf_span[ui] 行中从第 #cf_span[li] 列到第 #cf_span[ri] 列的格子。Andryusha 清楚地记得，没有两个障碍物位于同一行，并且每一行都至少有一个空格，即没有任何一行被障碍物完全占据。\\n\\n玩家可以从上方将一个弹珠投向机器的任意一列。弹珠会向下坠落，直到遇到一个障碍物，或从板子底部掉出。一旦弹珠遇到障碍物，它就会消失，但立即在该障碍物的左侧和右侧各生成两个新的弹珠。如果障碍物位于板子边缘，则两个新弹珠都会出现在与边缘相反的一侧。多个弹珠可以占据同一位置，且彼此不会阻碍运动。最终，所有弹珠都会从机器底部掉落。\\n\\n特别地，有时弹珠可以像穿过空格一样穿过障碍物。这是因为障碍物实际上是活的，当弹珠从极高处落下时它们会感到恐惧。更具体地说，如果一个弹珠从相对高度大于 #cf_span[si] 的位置下落（即它开始下落的位置严格高于 #cf_span[ui + si]），那么该障碍物会避开弹珠。如果弹珠从板子顶部投下，则认为其起始高度为 #cf_span[(h + 1)]。\\n\\nAndryusha 记得他曾向每一列都投下了一颗弹珠。请帮他计算最终从机器底部掉落的弹珠总数。由于答案可能很大，请对 #cf_span[109 + 7] 取模。\\n\\n第一行包含三个整数 #cf_span[h], #cf_span[w] 和 #cf_span[n]（#cf_span[1 ≤ h ≤ 109], #cf_span[2 ≤ w ≤ 105], #cf_span[0 ≤ n ≤ 105]），分别表示行数、列数和障碍物数量。\\n\\n接下来的 #cf_span[n] 行描述障碍物。第 #cf_span[i] 行包含四个整数 #cf_span[ui], #cf_span[li], #cf_span[ri] 和 #cf_span[si]（#cf_span[1 ≤ ui ≤ h], #cf_span[1 ≤ li ≤ ri ≤ w], #cf_span[1 ≤ si ≤ 109]），分别表示第 #cf_span[i] 个障碍物所在的行、左端列、右端列，以及障碍物不避开弹珠的最大相对下落高度。保证每行至少有一个空格，且所有 #cf_span[ui] 互不相同。\\n\\n输出一个整数——问题的答案对 #cf_span[109 + 7] 取模的结果。\\n\\n在第一个样例中，只有一个障碍物：如果从第二列或第三列投下弹珠，则会弹出两个弹珠，否则只弹出一个。总答案为 #cf_span[7]。\\n\\n在第二个样例中，最终弹珠数量按初始投弹列顺序依次为 #cf_span[2], #cf_span[2], #cf_span[4], #cf_span[4], #cf_span[4]。\\n\\n在第三个样例中，最终弹珠数量为 #cf_span[1], #cf_span[1], #cf_span[4], #cf_span[4], #cf_span[4]。注意，第一个障碍物会避开从板子顶部下落的弹珠，但不会避开从第二个障碍物弹出的弹珠。\\n\\n在第四个样例中，最终弹珠数量为 #cf_span[2], #cf_span[2], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[1], #cf_span[2], #cf_span[1], #cf_span[1], #cf_span[1], #cf_span[1]。下图展示了将弹珠投向第七列的情形。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含三个整数 #cf_span[h], #cf_span[w] 和 #cf_span[n]（#cf_span[1 ≤ h ≤ 109], #cf_span[2 ≤ w ≤ 105], #cf_span[0 ≤ n ≤ 105]），分别表示行数、列数和障碍物数量。接下来的 #cf_span[n] 行描述障碍物。第 #cf_span[i] 行包含四个整数 #cf_span[ui], #cf_span[li], #cf_span[ri] 和 #cf_span[si]（#cf_span[1 ≤ ui ≤ h], #cf_span[1 ≤ li ≤ ri ≤ w], #cf_span[1 ≤ si ≤ 109]），分别表示第 #cf_span[i] 个障碍物所在的行、左端列、右端列，以及障碍物不避开弹珠的最大相对下落高度。保证每行至少有一个空格，且所有 #cf_span[ui] 互不相同。\"},{\"iden\":\"output\",\"content\":\"输出一个整数——问题的答案对 #cf_span[109 + 7] 取模的结果。\"},{\"iden\":\"examples\",\"content\":\"输入10 5 13 2 3 10输出7输入10 5 23 1 3 105 3 5 10输出16输入10 5 23 1 3 75 3 5 10输出14输入10 15 47 3 9 56 4 10 11 1 4 104 11 11 20输出53\"},{\"iden\":\"note\",\"content\":\"在第一个样例中，只有一个障碍物：如果从第二列或第三列投下弹珠，则会弹出两个弹珠，否则只弹出一个。总答案为 #cf_span[7]。在第二个样例中，最终弹珠数量按初始投弹列顺序依次为 #cf_span[2], #cf_span[2], #cf_span[4], #cf_span[4], #cf_span[4]。在第三个样例中，最终弹珠数量为 #cf_span[1], #cf_span[1], #cf_span[4], #cf_span[4], #cf_span[4]。注意，第一个障碍物会避开从板子顶部下落的弹珠，但不会避开从第二个障碍物弹出的弹珠。在第四个样例中，最终弹珠数量为 #cf_span[2], #cf_span[2], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[6], #cf_span[1], #cf_span[2], #cf_span[1], #cf_span[1], #cf_span[1], #cf_span[1]。下图展示了将弹珠投向第七列的情形。 #cf_span(class=[tex-font-size-small], body=[The result of throwing a marble into the seventh column.]) \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ h, w, n \\in \\mathbb{Z} $ denote the number of rows, columns, and barriers, respectively. \nLet $ B = \\{ (u_i, l_i, r_i, s_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of barriers, where: \n- $ u_i \\in \\{1, \\dots, h\\} $ is the row of barrier $ i $, \n- $ [l_i, r_i] \\subseteq \\{1, \\dots, w\\} $ is the column interval it occupies, \n- $ s_i \\in \\mathbb{Z}^+ $ is the maximum relative fall height below which the barrier does **not** evade. \n\nLet $ M_j \\in \\mathbb{N} $ denote the number of marbles exiting the bottom when a single marble is initially dropped in column $ j \\in \\{1, \\dots, w\\} $. \n\n**Constraints** \n1. $ 1 \\le h \\le 10^9 $, $ 2 \\le w \\le 10^5 $, $ 0 \\le n \\le 10^5 $ \n2. All $ u_i $ are distinct. \n3. For each barrier $ i $, $ l_i \\le r_i $, and at least one cell in row $ u_i $ is free. \n4. A marble dropped from the top starts at height $ h+1 $. \n5. A barrier $ i $ evades a marble if the marble’s fall distance exceeds $ s_i $, i.e., if it started above row $ u_i + s_i $. \n6. When a marble hits a non-evading barrier at column $ c \\in [l_i, r_i] $, it splits into two marbles: one at $ c-1 $, one at $ c+1 $. \n - If $ c = 1 $, both marbles appear at column 2. \n - If $ c = w $, both marbles appear at column $ w-1 $. \n7. Marbles fall vertically until they hit a barrier or exit below row 1. \n\n**Objective** \nCompute: \n$$\n\\sum_{j=1}^{w} M_j \\mod (10^9 + 7)\n$$ \nwhere each $ M_j $ is determined by simulating the recursive splitting of marbles under barrier evasion rules, starting from column $ j $ at height $ h+1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF781E","tags":["data structures"],"sample_group":[["10 5 1\n3 2 3 10","7"],["10 5 2\n3 1 3 10\n5 3 5 10","16"],["10 5 2\n3 1 3 7\n5 3 5 10","14"],["10 15 4\n7 3 9 5\n6 4 10 1\n1 1 4 10\n4 11 11 20","53"]],"created_at":"2026-03-03 11:00:39"}}