在 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 翻译