题目描述

在 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$ 的值。

3 0
1 3
2 3
3 2

5

8 2
1 3
5 1
6 7
7 5
5 2
2 1
3 1
1 6

36

10 3
1 5
2 3
2 4
5 4
10 7
7 9
4 3
3 7
7 7
6 5

109

提示

【样例解释 #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$ 分）无附加限制。