Problem Description

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$?

Input Format

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 Format

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

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

11

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

Hint

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.

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