Supervision
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?
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.
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
Source: USA Computing Olympiad.
Input Format
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
Output the number of good subsets modulo 109+7.