P13738 [JOIGST 2025] 电波塔 / 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$ 的塔 $i_1, i_2$，当满足 $A_{i_2} \leq B_{i_1} \leq A_{i_2} + L$ 时，信息可从塔 $i_1$ 传输到塔 $i_2$。 EGOI 国政$ $府将通信稳定性定义为**满足顺序传输条件的非空子集数量**。具体来说，如果子集 $S = {i_1, i_2, \dots, i_k}$（$i_1 < i_2 < \cdots < i_k$）满足以下条件，则 $S$ 满足顺序传输条件： - 对于任意相邻的两座塔 $(i_j, i_{j+1})$（$1 \leq j \leq k-1$），都满足 $A_{i_{j+1}} \leq B_{i_j} \leq A_{i_{j+1}} + L$。 给定电波塔参数，计算符合条件的子集数量模 $10^9 + 7$ 的结果。

输入按以下格式从标准输入给出： > $N$ $L$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出一行，表示方案数模 $10^9 + 7$ 的值。

#### 【样例解释 #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$ 传输信息。 所以，这种选择方式满足条件。 满足条件的塔的选择方式有 $\lbrace1\rbrace, \lbrace2\rbrace, \lbrace3\rbrace, \lbrace1, 3\rbrace, \lbrace2, 3\rbrace$ 这 $5$ 种。因此，输出 $5\bmod (10^9 + 7) = 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$）。 - 输入的所有值都是整数。 #### 【子任务】 1. （$20$ 分）$N \leq 16$。 2. （$20$ 分）$N \leq 5\,000$。 3. （$25$ 分）$L = 0$。 4. （$35$ 分）无附加限制。