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\)?

Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi

SCORING

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

Problem credits: Agastya Goel, Eva Zhu, and Benjamin Qi

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\).

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Gold