配点: 100 点
在EGOI国家,东部和西部 N 无线电塔排列整齐,它们之间进行信息通信,为人们提供互联网通信。 在无线电塔上,从西边看去, 它们的编号最大为 1 从 N 。 无线电塔 i (1 \leqq i \leqq N) 表示波长来自西边。 A_i 以上 A_i + L 接收以下无线电波并向东 可以传输 B_i 无线电波。 换句话说, 当1 \leqq i_1 < i_2 \leqq N ,A_{i_2} \leqq B_{i_1} \leqq A_{i_2} + L 成立时,无线电塔 i_1 来自无线电塔 信息可以传送到 i_2 。
如今,EGOI 国家需要更稳定的互联网通信。 EGOI国家政府“安装了无线电塔,以便可以按数字顺序传输信息。” 1 我们决定使用所选方法的数量作为通信稳定性的标准。 具体而言,满足以下条件。 1 我想找到选择多个塔的方法数量。
- 按从小到大的顺序对选定的塔进行编号。 i_1, i_2, \dots, i_k ,全部 j (1\leqq j\leqq k-1)对于 A_{i_{j+1}} \leqq B_{i_j} \leqq A_{i_{j+1}} + L 成立。
给定无线电塔可以发射和接收的波长信息,计算选择满足条件的塔的方法数。 编写一个程序求除以 1\,000\,000\,007 后的余数。
入力
输入是按以下格式从标准输入给出的。
N L A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
将满足条件的塔选择方法的数量输出到标准输出。 除以 1\,000\,000\,007 后的余数 考虑选择 1 行。
制約
- 2 \leqq N \leqq 300\,000.
- 0 \leqq L \leqq 300\,000.
- 1 \leqq A_i \leqq 300\,000 (1\leqq i \leqq N).
- 1 \leqq B_i \leqq 300\,000 (1\leqq i \leqq N).
- 所有输入值均为整数。
小課題
- (20 点) N \leqq 16.
- (20 点) N \leqq 5\,000.
- (25 点) L = 0.
- (35 点)没有额外的限制。
入力例 1
3 0 1 3 2 3 3 2
出力例 1
5
電波塔 1, 2, 3 的情况。 因为它不是
- A_2 \leqq B_1 \leqq A_2 + L ,所以无线电塔 无法向 1 来自无线电塔 信息可以传送到 2 传达信息。
- A_3 \leqq B_2 \leqq A_3 + L ,所以无线电塔 可以将信息传输到 2 来自无线电塔 信息可以传送到 3 。
因此,该选择方法不满足条件。
電波塔 1, 3 的情况。 因为它不是
- A_3 \leqq B_1 \leqq A_3 + L ,所以无线电塔 可以将信息传输到 1 来自无线电塔 信息可以传送到 3 。
因此,该选择方法满足条件。
如何选择符合条件的塔:\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3\rbrace, \lbrace1, 3\rbrace, \lbrace2, 3\rbrace 的 5 没错。 因此, 它是除以5 它被转换为格式 1\,000\,000\,007 的余数 5 。
此输入示例满足所有子任务约束。
入力例 2
8 2 1 3 5 1 6 7 7 5 5 2 2 1 3 1 1 6
出力例 2
36
此输入示例是一个小作业。 1,2,4 满足约束。
入力例 3
10 3 1 5 2 3 2 4 5 4 10 7 7 9 4 3 3 7 7 7 6 5
出力例 3
109
此输入示例是一个小作业。 1,2,4 满足约束。