CF780G.Andryusha and Nervous Barriers

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.

Further, 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.

The 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.

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).

Andryusha 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.

安德柳沙发现了一台令人困惑的街机设备。该设备是一块垂直放置的方格板，分为若干正方形格子。板子有 $w$ 列，从左到右编号为 $1$ 到 $w$；有 $h$ 行，从下到上编号为 $1$ 到 $h$。

此外，板子的某些行中设置了障碍物。总共有 $n$ 个障碍物，其中第 $i$ 个障碍物占据第 $u_i$ 行中从第 $l_i$ 列到第 $r_i$ 列的所有格子。安德柳沙清楚地记得：任意两个障碍物不会位于同一行；而且，没有任何一行被障碍物完全占据，即每一行至少有一个空闲格子。

玩家可以从机器上方朝任意一列投掷弹珠。弹珠竖直下落，直到碰到某个障碍物，或直接穿过板子底部掉落。一旦弹珠碰到障碍物，它便立即消失，并在该障碍物正左方和正右方各自生成一颗新弹珠。若障碍物位于板子边缘（即最左列或最右列），则两颗新弹珠均出现在障碍物远离边缘的一侧（即都紧邻障碍物、位于板内一侧）。多个弹珠可同时占据同一格子，且互不阻碍彼此运动。最终，所有弹珠必将从机器底部掉落。

弹珠与障碍物相互作用的示例。

奇特的是，有时弹珠会像穿过空闲格子一样直接穿过障碍物。这是因为这些障碍物实际上是活的，当弹珠从极高处坠落时，它们会被吓跑。更准确地说：若一颗弹珠朝第 $i$ 个障碍物下落，且其相对高度超过 $s_i$（即它开始下落的位置严格高于 $u_i + s_i$），则该障碍物会躲避这颗弹珠。若弹珠从板子顶部投下，则视为其初始位置的高度为 $h + 1$。

安德柳沙记得自己曾向每一列各投掷过一颗弹珠。请帮他计算最终从机器底部掉落的弹珠总数。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

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.

Next 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.

第一行包含三个整数 $h$、$w$ 和 $n$（$1 \leq h \leq 10^9$，$2 \leq w \leq 10^5$，$0 \leq n \leq 10^5$），分别表示机器的行数、列数以及障碍物数量。

接下来 $n$ 行描述障碍物。其中第 $i$ 行包含四个整数 $u_i$、$l_i$、$r_i$ 和 $s_i$（$1 \leq u_i \leq h$，$1 \leq l_i \leq r_i \leq w$，$1 \leq s_i \leq 10^9$），分别表示第 $i$ 个障碍物所在的行号、最左列号、最右列号，以及该障碍物能承受下落弹珠的最大相对下落高度（超过此高度则障碍物无法阻挡弹珠）。保证每行至少存在一个空闲格子，且所有 $u_i$ 互不相同。

Print one integer — the answer to the problem modulo 109 + 7.

输出一个整数——该问题答案对 $10^9 + 7$ 取模的结果。

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.

In the second sample case, the numbers of resulting marbles are 2, 2, 4, 4, 4 in order of indexing columns with the initial marble.

In 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.

In 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.

The result of throwing a marble into the seventh column.

在第一个样例中，存在一个障碍物：若将弹珠投入第二列或第三列，则会滚出两个弹珠；否则仅滚出一个弹珠。总答案为 7。

在第二个样例中，按列索引顺序（即从初始弹珠所在列开始编号），最终滚出的弹珠数量依次为 2、2、4、4、4。

在第三个样例中，最终滚出的弹珠数量依次为 1、1、4、4、4。注意：第一个障碍物会避开从棋盘顶部下落的弹珠，但不会避开从第二个障碍物下落的弹珠。

在第四个样例中，最终滚出的弹珠数量依次为 2、2、6、6、6、6、6、6、6、1、2、1、1、1、1。下方图片展示了将弹珠投入第七列的情形。

将弹珠投入第七列的结果。