There are N(1≤N≤106) 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 pi (0≤pi≤109) 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≤109). How many good subsets are there, modulo 109+7?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two integers N and D.
The next N lines each contain two integers pi and oi. pi denotes the position the ith cow will move to. oi=1 means the ith cow is a coach, whereas oi=0 means the ith cow is a camper.
It is guaranteed that the pi are given in strictly increasing order.
OUTPUT FORMAT (print output to the terminal / stdout):
Output the number of good subsets modulo 109 +7.
SAMPLE INPUT:
6 1
3 1
4 0
6 1
7 1
9 0
10 0
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
13094
SCORING:
Input 3: N=20
Input 4: D=0
Inputs 5-8: N≤5000
Inputs 9-16: No additional constraints.
Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi