Page not loading? Try clicking here.
Placeholder

#8860
Subtask

Supervision 1s 1024MB

Problems

There are N (1≤N≤10^6) cows in cow camp, labeled 1…N. Each cow is either a camper or a coach.

A nonempty subset of the cows will be selected to attend a field trip. If the ith cow is selected, the cow will move to position p_i (0≤p_i≤10^9) on a number line, where the array p is strictly increasing.

A nonempty subset of the cows is called "good" if for every selected camper, there is a selected coach within D units to the left, inclusive (0≤D≤10^9). How many good subsets are there, modulo 10^9+7?


Input

The first line contains two integers N and D.

The next N lines each contain two integers p_i and o_i. p_i denotes the position the i

th cow will move to. o_i=1 means the i th cow is a coach, whereas o_i=0 means the i th cow is a camper.

It is guaranteed that the p_i are given in strictly increasing order.


Output

Output the number of good subsets modulo 10^9+7.


Subtask

# Score Condition
#110

N=20

#220

D=0

#330

N\le 5000

#440

No additional constraints.


Example #1

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

The last two campers can never be selected. All other nonempty subsets work as long as if cow 2 is selected, then cow 1 is also selected.


Example #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

Source

USACO 2026 First Contest, Gold

You must sign in to write code.