{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"Print one integer — the answer to the problem modulo 109 + 7."},{"iden":"examples","content":"Input\n\n10 5 1\n3 2 3 10\n\nOutput\n\n7\n\nInput\n\n10 5 2\n3 1 3 10\n5 3 5 10\n\nOutput\n\n16\n\nInput\n\n10 5 2\n3 1 3 7\n5 3 5 10\n\nOutput\n\n14\n\nInput\n\n10 15 4\n7 3 9 5\n6 4 10 1\n1 1 4 10\n4 11 11 20\n\nOutput\n\n53"},{"iden":"note","content":"In 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."}],"translated_statement":[{"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[i] 个障碍物下落，则该障碍物会避开弹珠。如果弹珠从板子顶部投下，则认为其起始高度为 #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.]) "}],"sample_group":[],"show_order":[],"formal_statement":"**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, h] $ is the row of barrier $ i $, \n- $ [l_i, r_i] \\subseteq [1, w] $ is the column range it occupies, \n- $ s_i \\in [1, 10^9] $ is the maximum relative fall height below which the barrier does **not** evade. \n\nLet $ H = h + 1 $ be the initial height from which marbles are dropped. \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. For each barrier $ i $, $ 1 \\le s_i \\le 10^9 $. \n\n**Objective** \nFor each initial column $ j \\in \\{1, \\dots, w\\} $, simulate the descent of a marble dropped from height $ H $, following these rules: \n- A marble falls vertically downward until it hits a barrier in its column. \n- If the marble reaches barrier $ i $ at row $ u_i $, and its fall distance from $ H $ to $ u_i $ is $ H - u_i $, then: \n - If $ H - u_i > s_i $, the barrier **evades**; the marble continues falling. \n - Otherwise, the barrier **stops** the marble, and **two new marbles** are spawned at positions $ j-1 $ and $ j+1 $, at height $ u_i + 1 $. \n- If $ j = 1 $ and a marble hits the left edge, both spawned marbles appear at column $ 2 $. \n- If $ j = w $ and a marble hits the right edge, both spawned marbles appear at column $ w-1 $. \n- Marbles fall through the bottom (row 0) and are counted as output. \n- Multiple marbles may occupy the same cell; they do not interfere. \n\nLet $ f(j) $ be the total number of marbles that exit the bottom when starting from column $ j $. \nCompute: \n$$\n\\sum_{j=1}^{w} f(j) \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}