AT_joigsp2025_j 電波塔 (Radio Towers)

在 EGOI 国，有 $N$ 根无线电塔沿东西方向排列，通过这些电塔之间的信息通信为国民提供互联网服务。无线电塔按照从西到东的顺序编号为 $1$ 到 $N$。编号为 $i$ 的电塔（$1 \leq i \leq N$），能够接收从西方传来的波长不小于 $A_i$ 且不大于 $A_i + L$ 的电波，并且能够向东方发射波长为 $B_i$ 的电波。也就是说，对于 $1 \leq i_1 < i_2 \leq N$，当 $A_{i_2} \leq B_{i_1} \leq A_{i_2} + L$ 时，可以从电塔 $i_1$ 向电塔 $i_2$ 传递信息。 最近，EGOI 国对互联网通信的稳定性提出了更高要求。EGOI 国政府决定以“能够按顺序编号进行信息传递的电塔选取方案数”作为通信稳定性的标准。具体来说，希望求出满足以下条件的选取 $1$ 根及以上电塔的方案数： - 设选中的电塔按编号从小到大依次为 $i_1, i_2, \dots, i_k$，则对于所有 $j$（$1 \leq j \leq k-1$），必须有 $A_{i_{j+1}} \leq B_{i_j} \leq 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. （$20$ 分）$N \leq 16$。 2. （$20$ 分）$N \leq 5\,000$。 3. （$25$ 分）$L = 0$。 4. （$35$ 分）无额外限制。 --- ## 样例解释1 考虑选择电塔 $1,2,3$ 的情况。 - 由于不满足 $A_2 \leq B_1 \leq A_2 + L$，因此无法从电塔 $1$ 向电塔 $2$ 传递信息。 - 满足 $A_3 \leq B_2 \leq A_3 + L$，所以可以从电塔 $2$ 向电塔 $3$ 传递信息。 因此，这种选法不满足条件。 再考虑选择电塔 $1,3$ 的情况。 - 满足 $A_3 \leq B_1 \leq A_3 + L$，可以从电塔 $1$ 向电塔 $3$ 传递信息。 因此，这种选法满足条件。 所有满足条件的选法为 $\{1\}$、$\{2\}$、$\{3\}$、$\{1,3\}$、$\{2,3\}$，共 $5$ 种。因此，输出 $5$ 对 $1\,000\,000\,007$ 取模也为 $5$。 该输入样例满足所有子任务的限制。 --- ## 样例解释2 该输入样例满足子任务 $1,2,4$ 的限制。 --- ## 样例解释3 该输入样例满足子任务 $1,2,4$ 的限制。 # 数据范围 - $2 \leq N \leq 300\,000$。 - $0 \leq L \leq 300\,000$。 - $1 \leq A_i \leq 300\,000$（$1 \leq i \leq N$）。 - $1 \leq B_i \leq 300\,000$（$1 \leq i \leq N$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译