题目描述

奶牛营地有 $N$ 头（$1\le N \leq 10^6$）奶牛，编号为 $1\dots N$。每头奶牛要么是营员，要么是教练。

将选择一个非空的奶牛子集去参加实地考察。如果第 $i$ 头奶牛被选中，它将移动到数轴上的位置 $p_i$（$0\le p_i \leq 10^9$），其中数组 $p$ 是严格递增的。

一个非空子集被称为好的，当且仅当对于每个被选中的营员，在其左侧（含）距离 $D$ ($0\le D \leq 10^9$) 单位内，都存在一个被选中的教练。求有多少个好子集？结果对 $10^9+7$ 取模。

输入格式

第一行包含两个整数 $N$ 和 $D$。

接下来的 $N$ 行，每行包含两个整数 $p_i$ 和 $o_i$。$p_i$ 表示第 $i$ 头奶牛将移动到的位置。$o_i=1$ 表示第 $i$ 头奶牛是教练，而 $o_i=0$ 表示第 $i$ 头奶牛是营员。

保证 $p_i$ 按严格递增顺序给出。

输出格式

输出好子集的数量对 $10^9 + 7$ 取模的结果。

6 1
3 1
4 0
6 1
7 1
9 0
10 0

11

20 24
3 0
14 0
17 1
20 0
21 0
22 1
28 0
30 0
32 0
33 1
38 0
40 0
52 0
58 0
73 0
75 0
77 1
81 1
84 1
97 0

13094

提示

最后两头营员永远不能被选中。其他所有非空子集都是好的，只要当奶牛 $2$ 被选中时，奶牛 $1$ 也被选中。

• 输入 $3$：$N=20$
• 输入 $4$：$D=0$
• 输入 $5$-$8$：$N\le 5000$
• 输入 $9$-$16$：无额外约束。

翻译由 DeepSeek V3 完成