点击此处下载附加样例文件

题目描述

Farmer John 的 n 头牛站在了数轴上，自左向右依次编号为 1 ~ n，编号为 i 的牛在数轴上的位置为 $X_i$，性别为 $S_i$（$S_i$ ∈ {0,1}，$S_i=0$ 表示母牛，$S_i=1$ 表示公牛）。任意两头牛不会站在同一位置上。

John 要从中选择若干头牛去参加歌唱比赛，要求：

对于每名被选中的母牛，在其左侧与其距离不超过 d 的范围内至少有一头公牛被选中。

John 想知道，他有多少种选择方案？

你能帮助他吗？答案可能很大，你需要输出答案 mod 1,000,000,007 的值。

输入格式

第一行：两个整数 n, d。

接下来 n 行，每行两个整数 $X_i, S_i$。(数据保证 $X_1 < X_2 < …… < X_n$)

输出格式

一个整数，表示答案 mod 1,000,000,007。

输入样例

5 2
1 1
3 0
5 0
6 1
10 0

输出样例

5

样例解释

5 种选择方案为：

选择编号为 1 的牛；

选择编号为 4 的牛；

选择编号为 1, 4 的牛；

选择编号为 1, 2 的牛；

选择编号为 1, 2, 4 的牛。

数据范围

10% 的数据：$n ≤ 20$

另有 10% 的数据：$d = 0$

另有 10% 的数据：$n ≤ 5000$

70% 的数据：$1 ≤ n ≤ 10^6$

100% 的数据：$1 ≤ n ≤ 10^7$, $0 ≤ d, X_i ≤ 10^9$，$S_i$ ∈ {0,1}, 数据保证 $X_1 < X_2 < …… < X_n$

提示

本题输入量较大 需要快读：

uint8_t buf[1<<20], *p1, *p2;
#define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<20,stdin)),*p1++)
int read() {
	int k = 0, c = gc();
	for (; !isdigit(c); c = gc()) ;
	for (; isdigit(c); c = gc()) k = k * 10 + (c ^ 48);
	return k;
}