题目描述

有 $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$。

求一共有多少个 非空电视塔子集 满足：

• 设电视塔子集的大小为 $k$。
• 对于任意相邻的两座塔 $i,i+1$ 其中 $(1\leq i<k)$，使得电视塔 $i$ 可以传输信息到电视塔 $i+1$。

由于满足要求的答案可能很大，计算符合条件的子集数量模 $10^9 + 7$ 的结果。

输入格式

第一行输入 $n$ 和 $L$。

接下来 $n$ 行，每行两个整数 $a_i,b_i$。

输出格式

输出一行，表示方案数模 $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$ 传输信息。

所以，这种选择方式不满足条件。

考虑选择电波塔 $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$。

数据范围

对于 $100\%$ 的数据满足：$2 \leq n \leq 3\times 10^5$，$0 \leq L \leq 3\times 10^5$，$1 \leq a_i,b_i \leq 3\times 10^5$。

• 子任务 1（$20$ 分）$n \leq 16$。
• 子任务 2（$20$ 分）$n \leq 5\,000$。
• 子任务 3 （$25$ 分）$L = 0$。
• 子任务 4 （$35$ 分）无附加限制。