← 返回题目列表

AtCoder · joigsp2025_j

J. 无线电塔

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值均为整数。

小課題

  1. (20 点) N \leqq 16.
  2. (20 点) N \leqq 5\,000.
  3. (25 点) L = 0.
  4. (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 满足约束。