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.
<center> Examples of marble-barrier interaction.</center>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.
## Input
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.
## Output
Print one integer — the answer to the problem modulo 109 + 7.
[samples]
## Note
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.
<center> The result of throwing a marble into the seventh column.</center>
**Definitions**
Let $ h, w, n \in \mathbb{Z} $ denote the number of rows, columns, and barriers respectively.
Let $ B = \{ (u_i, l_i, r_i, s_i) \mid i \in \{1, \dots, n\} \} $ be the set of barriers, where:
- $ u_i \in [1, h] $ is the row of barrier $ i $,
- $ [l_i, r_i] \subseteq [1, w] $ is the column range it occupies,
- $ s_i \in [1, 10^9] $ is the maximum relative fall height below which the barrier does **not** evade.
Let $ H = h + 1 $ be the initial height from which marbles are dropped.
**Constraints**
1. $ 1 \le h \le 10^9 $, $ 2 \le w \le 10^5 $, $ 0 \le n \le 10^5 $
2. All $ u_i $ are distinct.
3. For each barrier $ i $, $ l_i \le r_i $, and at least one cell in row $ u_i $ is free.
4. For each barrier $ i $, $ 1 \le s_i \le 10^9 $.
**Objective**
For each initial column $ j \in \{1, \dots, w\} $, simulate the descent of a marble dropped from height $ H $, following these rules:
- A marble falls vertically downward until it hits a barrier in its column.
- If the marble reaches barrier $ i $ at row $ u_i $, and its fall distance from $ H $ to $ u_i $ is $ H - u_i $, then:
- If $ H - u_i > s_i $, the barrier **evades**; the marble continues falling.
- Otherwise, the barrier **stops** the marble, and **two new marbles** are spawned at positions $ j-1 $ and $ j+1 $, at height $ u_i + 1 $.
- If $ j = 1 $ and a marble hits the left edge, both spawned marbles appear at column $ 2 $.
- If $ j = w $ and a marble hits the right edge, both spawned marbles appear at column $ w-1 $.
- Marbles fall through the bottom (row 0) and are counted as output.
- Multiple marbles may occupy the same cell; they do not interfere.
Let $ f(j) $ be the total number of marbles that exit the bottom when starting from column $ j $.
Compute:
$$
\sum_{j=1}^{w} f(j) \mod (10^9 + 7)
$$