Andryusha 发现了一台令人费解的街机。该机器是一块垂直调整的板,分为方形单元。棋盘有 w 列,从左到右编号为 1 到 w,h 行从下到上编号为 1 到 h。
此外,一些板行中存在障碍物。总共有 n 个障碍,其中第 i 个障碍占据了 ui 行的 li 到 ri 单元格。 Andryusha 记得很清楚,没有两个障碍物共用同一排。此外,没有一行完全被屏障占据,即每行中至少有一个单元是空闲的。
玩家可以从上方向机器的任意柱投掷弹珠。弹珠向下落,直到遇到障碍物,或落入棋盘底部。一旦遇到障碍物,弹珠就会消失,但会被同一障碍物左侧和右侧的另外两个弹珠取代。在障碍物位于棋盘边缘的情况下,两个弹珠都会出现在与边缘相对的一侧的障碍物旁边。多个弹珠可以占据棋盘的同一位置,而不会妨碍彼此的移动。最终,所有弹珠都必然从机器底部掉落。
大理石与屏障相互作用的示例。
奇怪的是,有时弹珠可以像自由细胞一样穿过障碍物。之所以如此,是因为这些屏障实际上是活的,当弹珠从很高的高度向它们袭来时,它们就会受到惊吓。更具体地说,如果弹珠从高于 si 的相对高度落向障碍物 i(即,它开始下落的高度严格高于 ui + si),则障碍物会避开弹珠。如果从棋盘顶部抛出一个弹珠,则认为它出现在高度 (h + 1) 处。
Andryusha 记得在每根柱子里扔过一次弹珠。帮助他找出落在机器底部的弹珠总数。由于答案可能很大,因此将其打印为 109 + 7 模。
输入
第一行包含三个整数 h、w 和 n (1 ≤ h ≤ 109, 2 ≤ w ≤ 105, 0 ≤ n ≤ 105)——分别是机器中的行数、列数和栅栏数。
接下来的 n 行描述了障碍。其中第 i 行包含四个整数 ui、li、ri 和 si(1 ≤ ui ≤ h、1 ≤ li ≤ ri ≤ w、1 ≤ si ≤ 109)——行索引、第 i 个障碍物的最左和最右列索引,以及障碍物无法躲避下落弹珠的最大相对下落高度。保证每一行至少有一个空闲单元,并且所有 ui 都是不同的。
输出
打印一个整数——以 109 + 7 为模的问题的答案。
示例
输入 #1
10 5 1 3 2 3 10
输出 #1
7
输入 #2
10 5 2 3 1 3 10 5 3 5 10
输出 #2
16
输入 #3
10 5 2 3 1 3 7 5 3 5 10
输出 #3
14
输入#4
10 15 4 7 3 9 5 6 4 10 1 1 1 4 10 4 11 11 20
输出#4
53
注意
在第一个示例案例中,有一个障碍:如果有人在第二列或第三列中扔一个弹珠,则会出现两个弹珠,否则只有一个弹珠。总答案是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。下图显示了弹珠被扔进第七列的情况。
将弹珠扔进第七根柱子的结果。