题目描述

夏令营里有 \(N\) 头奶牛，编号为 \(1 \dots N\)，满足 \(1 \le N \le 10^6\)。每头奶牛要么是营员，要么是教练。

现在要从中选出一个非空子集参加一次郊游。

如果第 \(i\) 头奶牛被选中，它会移动到数轴上的位置 \(p_i\)，满足 \(0 \le p_i \le 10^9\)，并且数组 \(p\) 严格递增。

如果一个非空子集满足下面的条件，就称它是“好的”：

• 对于子集中每一头被选中的营员，都必须存在一头同样被选中的教练，且这头教练位于它左侧不超过 \(D\) 的范围内（可以正好相距 \(D\)）

也就是说，对每个被选中的营员 \(i\)，必须存在一个被选中的教练 \(j\)，满足：

\(p_i - D \le p_j \le p_i\)

并且 \(j\) 在 \(i\) 左侧。

请你求出好的非空子集个数，对 \(10^9+7\) 取模。

输入格式

第一行包含两个整数 \(N\) 和 \(D\)。

接下来 \(N\) 行，每行两个整数 \(p_i\) 和 \(o_i\)：

• \(p_i\) 表示第 \(i\) 头奶牛移动后的位置
• 若 \(o_i = 1\)，表示它是教练
• 若 \(o_i = 0\)，表示它是营员

保证输入中的 \(p_i\) 已按严格递增顺序给出。

输出格式

输出一个整数，表示答案对 \(10^9+7\) 取模后的结果。

样例 1

输入

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

输出

11

说明

最后两个营员永远无法被选中。其余所有非空子集都合法，但如果选择了第 \(2\) 头奶牛，则第 \(1\) 头奶牛也必须被选。

样例 2

输入

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

数据范围

• 输入 3：\(N = 20\)
• 输入 4：\(D = 0\)
• 输入 5-8：\(N \le 5000\)
• 输入 9-16：无额外限制

命题信息

原题命题：Agastya Goel、Eva Zhu、Benjamin Qi