Bạn vừa đến Vilnius và muốn ghé thăm các thành phố khác nhau ở Litva.

Các thành phố ở Litva nằm trên một đường thẳng và được đánh số lần lượt từ \(1\) đến \(N\). Vilnius mang số \(1\).

Mỗi thành phố có một nhà ga với đúng một tuyến tàu xuất phát từ đó. Bạn chỉ có thể lên tàu ở ga đầu của tuyến, nhưng có thể xuống tại bất kỳ điểm dừng nào của tàu. Tàu xuất phát từ thành phố \(i\) dừng lại sau mỗi \(d_i\) thành phố và có \(x_i\) điểm dừng trên tuyến, không tính thành phố xuất phát. Nếu \(d_i=0\), tàu xuất phát từ thành phố \(i\) hiện không hoạt động và bạn không thể lên tàu đó.

Cụ thể, nếu lên tàu tại thành phố \(i\), bạn có thể xuống tại bất kỳ thành phố nào mang số \(i+t\cdot d_i\), với \(1\le t\le x_i\). Vì chỉ muốn ghé thăm các thành phố ở Litva, bạn sẽ không đi quá thành phố \(N\), ngay cả khi tuyến tàu còn những điểm dừng phía sau.

Bạn dự định ghé thăm một số thành phố và dùng tàu để di chuyển giữa chúng. Khi lập kế hoạch, bạn muốn biết có bao nhiêu hành trình khác nhau bắt đầu tại Vilnius. Hai hành trình khác nhau nếu dãy thành phố mà bạn dừng lại trong hai hành trình khác nhau.

Hãy tính số hành trình này và in ra kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) là số thành phố.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(d_i\) và \(x_i\) mô tả tuyến tàu xuất phát từ thành phố \(i\).

Dữ liệu ra

In ra một số nguyên duy nhất là số cách ghé thăm một số trong \(N\) thành phố, lấy modulo \(10^9+7\).

Ràng buộc

• \(1\le N\le 10^5\).
• \(0\le d_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le x_i\le 10^9\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 15\).
2. \(13\) điểm: \(N\le 10^4\).
3. \(16\) điểm: \(d_i=1\) với mọi \(1\le i\le N\).
4. \(34\) điểm: \(x_i=10^9\) với mọi \(1\le i\le N\).
5. \(29\) điểm: không có ràng buộc bổ sung.

Ví dụ

5
1 3
2 1
1 3
0 10
3 5

7