Có \(N\) (\(1\leq N\leq 10^6\)) con bò tại trại hè dành cho bò, được đánh số \(1\dots N\). Mỗi con bò là một trại viên hoặc một huấn luyện viên.

Một tập con không rỗng của các con bò sẽ được chọn để tham gia một chuyến dã ngoại. Nếu con bò thứ \(i\) được chọn, nó sẽ di chuyển đến vị trí \(p_i\) (\(0\leq p_i\leq 10^9\)) trên một trục số, trong đó mảng \(p\) tăng nghiêm ngặt.

Một tập con không rỗng của các con bò được gọi là "tốt" nếu với mỗi trại viên được chọn, có một huấn luyện viên được chọn nằm trong phạm vi \(D\) đơn vị về bên trái, kể cả điểm trại viên đang đứng (\(0\leq D\leq 10^9\)). Có bao nhiêu tập con tốt, theo modulo \(10^9+7\)?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(p_i\) và \(o_i\). \(p_i\) biểu thị vị trí mà con bò thứ \(i\) sẽ di chuyển đến. \(o_i=1\) có nghĩa con bò thứ \(i\) là huấn luyện viên, còn \(o_i=0\) có nghĩa con bò thứ \(i\) là trại viên.

Đảm bảo các giá trị \(p_i\) được cho theo thứ tự tăng nghiêm ngặt.

Dữ liệu ra

In ra số tập con tốt theo modulo \(10^9+7\).

Ví dụ

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

Phân nhóm

• Dữ liệu vào 3: \(N=20\).
• Dữ liệu vào 4: \(D=0\).
• Dữ liệu vào 5–8: \(N\leq 5000\).
• Dữ liệu vào 9–16: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “Supervision”. Tác giả đề: Agastya Goel, Eva Zhu và Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1547