Supervision

There are $N$ ($1\le N \leq 10^6$) cows in cow camp, labeled $1\dots 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 $i$th cow is selected, the cow will move to position $p_i$ ($0\le p_i \leq 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\le D\le 10^9$). How many good subsets are there, modulo $10^9+7$?

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.

• Input 3: $N=20$
• Input 4: $D=0$
• Inputs 5-8: $N\le 5000$
• Inputs 9-16: No additional constraints.

Output the number of good subsets modulo $10^9 + 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.