页面无法加载？点击这里可能会修复。
Placeholder

#8860
子任务

감독 1s 1024MB

问题

소 캠프에는 1…N번의 번호가 붙은 N (1≤N≤10^6)마리의 소가 있습니다. 각 소는 캠퍼 또는 코치 중 하나입니다.

현장 학습에 참여할 소들의 비어 있지 않은 부분 집합이 선택됩니다. 만약 i번째 소가 선택되면, 그 소는 수직선 상의 p_i (0≤p_i≤10^9) 위치로 이동하며, 배열 p는 엄격하게 증가합니다.

선택된 모든 캠퍼에 대해, 왼쪽으로 D 단위 이내(경계 포함, 0≤D≤10^9)에 선택된 코치가 존재한다면, 소들의 비어 있지 않은 부분 집합을 "좋은(good)" 부분 집합이라고 부릅니다. 좋은 부분 집합은 몇 개입니까? (단, 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로 나눈 나머지를 출력하세요.


子任务

编号 分数 条件
#110分

N=20

#220分

D=0

#330分

N\le 5000

#440分

추가 제약 조건 없음


示例 #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

来源

USACO 2026 First Contest, Gold
需要登录才能编写代码。