Dọc theo một con đường dài, có các cột đèn trên đó có $n$ chiếc đèn lồng. Hãy giới thiệu một hệ tọa độ dọc theo con đường. Cột đèn mà chiếc đèn thứ $i$ được đặt ở tọa độ $x_i$. Trong sáu subtask đầu tiên của bài toán này, trị giá 85 điểm, không có hai chiếc đèn nào được gắn trên cùng một cột, tức là tất cả các giá trị $x_i$ đều phân biệt. Trong hai subtask cuối, mỗi cột đèn có thể có tối đa hai chiếc đèn.
Để chiếu sáng con đường, một số chiếc đèn có thể được bật lên. Một chiếc đèn đang hoạt động với chỉ số $i$ có độ sáng $s_i$. Nó chiếu sáng sao cho chiếu sáng một đoạn liên tục của con đường có độ dài $s_i$ mét tính từ cột đèn mà nó được đặt. Mỗi chiếc đèn đang hoạt động có thể được hướng sang trái hoặc sang phải. Nếu chiếc đèn thứ $i$ được hướng sang trái, nó chiếu sáng đoạn đường $[x_i - s_i, x_i]$, và nếu hướng sang phải, thì $[x_i, x_i + s_i]$.
Hãy chọn một tập hợp khác rỗng các chiếc đèn để bật lên nhằm chiếu sáng một đoạn của con đường. Ta sẽ gọi tập hợp các đèn này là tiết kiệm nếu có thể hướng từng chiếc đèn đã chọn sang trái hoặc sang phải sao cho thỏa mãn hai điều kiện:
- các đoạn được chiếu sáng tạo thành một đoạn liên tục của con đường;
- không có đoạn nào có độ dài khác không được chiếu sáng bởi hai hay nhiều đèn cùng lúc.
Hình dưới đây cho thấy các tập con tiết kiệm gồm hai chiếc đèn cho mẫu thứ hai từ đề bài và các cách chiếu sáng một đoạn liên tục của con đường. Độ sáng của mỗi đèn được ghi phía trên nó.
Tìm số lượng tập con tiết kiệm của các chiếc đèn. Đưa ra phần dư của giá trị này khi chia cho $10^9 + 7$.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$) — số lượng chiếc đèn. Tiếp theo là mô tả các chiếc đèn.
Mỗi dòng trong số $n$ dòng tiếp theo chứa hai số nguyên $x_i$ và $s_i$ — tọa độ của cột đèn nơi đặt chiếc đèn thứ $i$ và độ sáng của nó ($1 \le x_i \le 5 \cdot 10^5$, $1 \le s_i \le 5 \cdot 10^5$, $x_1 \le x_2 \le \dots \le x_n$).
Dữ liệu đảm bảo có tối đa hai chiếc đèn được đặt trên cùng một cột, tức là với mỗi $v$ có tối đa hai chỉ số $i$ sao cho $x_i = v$.
Dữ liệu ra
Đưa ra một số nguyên — phần dư của phép chia số cách chọn một tập con tiết kiệm của các chiếc đèn cho $10^9 + 7$.
Nhiệm vụ con
Ta đưa vào một biến $t$ — số lượng tối đa các chiếc đèn có thể có cùng tọa độ $x_i$.
Nếu $t = 1$, thì $x_1 < x_2 < \dots < x_n$.
Nếu $t = 2$, thì $x_1 \le x_2 \le \dots \le x_n$, và nếu $x_i = x_{i+1}$, thì $x_{i-1} < x_i$ và $x_{i+1} < x_{i+2}$ (nếu các đèn tương ứng tồn tại).
| Nhiệm vụ con | Điểm | $t$ | $n$ | Ràng buộc bổ sung | Nhiệm vụ con yêu cầu |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | Với hai đèn phân biệt bất kỳ $i, j$, $x_i - s_i \ne x_j$ và $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | Với hai đèn phân biệt bất kỳ $i, j$, $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | Với hai đèn phân biệt bất kỳ $i, j$, $s_i = s_j$ | ||
| 5 | 10 | $t = 1$ | $n \le 1000$ | $s_i, x_i \le 1000$ | |
| 6 | 20 | $t = 1$ | 1 – 5 | ||
| 7 | 10 | $t = 2$ | Nếu $x_i = x_{i+1}$, thì $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Ví dụ, 1 – 7 |
Ví dụ
Dữ liệu vào 1
2 2 3 7 2
Dữ liệu ra 1
3
Dữ liệu vào 2
3 1 1 3 1 4 2
Dữ liệu ra 2
6
Dữ liệu vào 3
5 3 2 4 2 5 2 6 2 7 2
Dữ liệu ra 3
10
Dữ liệu vào 4
4 3 2 7 4 7 4 8 2
Dữ liệu ra 4
8
Dữ liệu vào 5
5 1 2 1 3 2 1 2 2 4 1
Dữ liệu ra 5
19
Ghi chú
Trong ví dụ đầu tiên, cả ba tập con khác rỗng của các chiếc đèn đều là tiết kiệm.
Trong ví dụ thứ hai, tất cả các tập con của các chiếc đèn đều là tiết kiệm, ngoại trừ tập $\{1, 2, 3\}$.