| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 11 | 10 | 10 | 90.909% |
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.
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
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.
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