소 캠프에는 \(1\)번부터 \(N\)번까지 번호가 붙은 \(N\)마리의 소가 있다. \((1 \le N \le 1,000,000)\) 각 소는 캠퍼 또는 코치 중 하나이다.

현장 학습에 참가할 소로 이루어진 공집합이 아닌 부분집합 하나를 선택한다. \(i\)번째 소가 선택되면 수직선 위의 좌표 \(p_i\)로 이동한다. \((0 \le p_i \le 10^9)\) 배열 \(p\)는 엄격한 오름차순이다.

선택된 모든 캠퍼에 대하여, 그 캠퍼의 왼쪽에서 거리가 \(D\) 이하인 위치에 선택된 코치가 한 마리 이상 있다면 이 부분집합을 좋은 부분집합이라고 한다. 거리 \(D\)인 경우도 포함한다. \((0 \le D \le 10^9)\)

좋은 부분집합의 개수를 \(1,000,000,007\)로 나눈 나머지를 구하여라.

입력

첫째 줄에 두 정수 \(N\)과 \(D\)가 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에 두 정수 \(p_i\)와 \(o_i\)가 공백으로 구분되어 주어진다. \(p_i\)는 \(i\)번째 소가 이동할 위치를 나타낸다. \(o_i=1\)이면 \(i\)번째 소는 코치이고, \(o_i=0\)이면 캠퍼이다.

\(p_i\)는 엄격한 오름차순으로 주어진다.

출력

좋은 부분집합의 개수를 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

11

예제 설명 1

마지막 두 캠퍼는 어떤 좋은 부분집합에도 선택될 수 없다. 나머지 소들로 이루어진 공집합이 아닌 부분집합 중에서는 \(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

예제 출력 2

13094

출처

USACO 2026 First Contest, Gold, Problem 3. Supervision