Có \(n\) quả bom nằm trên một đoạn thẳng. Quả bom thứ \(i\) \((1 \leq i \leq n)\) ở vị trí \(x_i\) và có bán kính nổ là \(r_i\). Khi quả bom thứ \(i\) nổ sẽ kích nổ các quả bom \(j\) mà \(x_i - r_i \leq x_j \leq x_i + r_i\).

Để tiến hành việc tháo dỡ \(n\) quả bom này, bạn cần tính toán độ nguy hiểm của mỗi quả bom. Độ nguy hiểm của quả bom thứ \(i\) là \(c_i\) - số quả bom sẽ bị nổ nếu ban đầu
ta chỉ kích nổ quả bom thứ \(i\).

Yêu cầu: Hãy tính \(S = \sum_{i=1}^{n} i \times c_i\). Vì \(S\) có thể rất lớn nên chỉ cần đưa ra số dư trong phép chia \(S\) cho \(({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 5 \times {10}^5)\) là số quả bom.
• \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) gồm hai số nguyên \(x_i, r_i\) \((-{10}^9 \leq x_i \leq {10}^9, 0 \leq r_i \leq 2 \times {10}^9)\).

Đảm bảo rằng \(x_i \leq x_{i+1}\), \(\forall 1 \leq i < n\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 (\(18\%\) số điểm): \(n \leq 5000\).
• Subtask 2 (\(29\%\) số điểm): \(r_i = 1\), \(\forall 1 \leq i \leq n\).
• Subtask 3 (\(53\%\) số điểm): Không có giới hạn gì thêm.

3
1 1
3 3
10 10

14