Tàu điện

Khu du lịch \(A\) đang xây dựng một hệ thống tàu điện để di chuyển giữa các điểm du lịch, dự kiến sẽ có \(X\) (\(X \le 2 \times 10^6\)) nhà ga. Hiện tại khu du lịch chỉ mới hoàn thiện và đưa vào sử dụng \(N\) nhà ga, các nhà ga được đánh số thứ tự từ trái sang phải với các số hiệu từ \(1\) đến \(N\). Trên một tuyến hành trình từ nhà ga \(1\) đến nhà ga \(N\), tàu điện chỉ có thể đi đến các nhà ga bên phải nó. Khi lên tàu tại nhà ga \(i\), hành khách phải trả tiền vé là \(c_i\) và chỉ được phép xuống tàu tại các nhà ga có số hiệu từ \(i + l_i\) đến \(i + r_i\) với \(1 \le i \le N\); \(1 \le l_i \le r_i \le N\).

Bạn Tâm đến khu du lịch \(A\) để trải nghiệm việc đi lại bằng tàu điện. Bạn Tâm muốn khám phá tất cả các cách đi khác nhau để có thể đi từ nhà ga \(1\) đến nhà ga \(N\). Hai cách đi được gọi là khác nhau nếu trên đường đi của chúng tồn tại ít nhất một nhà ga khác nhau. Ban quản lý khu du lịch cần biết tổng tiền vé của tất cả các cách đi khác nhau từ nhà ga \(1\) đến nhà ga \(N\) để báo giá cho bạn Tâm.

Yêu cầu: Hãy giúp ban quản lý khu du lịch giải quyết bài toán trên.

Input

• Dòng thứ nhất ghi số nguyên dương \(N\) (\(1 \le N \le 10^6\)) là số lượng nhà ga.

• Dòng thứ hai ghi \(N\) số nguyên dương \(c_1, c_2, \ldots, c_N\) (\(1 \le c_i \le 10^9\)) lần lượt là giá vé mà hành khách phải mua tại các nhà ga từ nhà ga \(1\) đến nhà ga \(N\).

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo: ghi hai số nguyên dương \(l_i, r_i\) (\(1 \le l_i \le r_i \le N\)), cho biết hành khách lên tàu tại nhà ga \(i\) có thể xuống tàu tại các nhà ga có số hiệu từ \(i + l_i\) đến \(i + r_i\). Lưu ý: \(i + l_i\) và \(i + r_i\) có thể lớn hơn \(N\) (khi đó nhà ga đó chưa hoàn thiện, không thể đến được; tuy nhiên chúng không vượt quá \(X\)).
  Các số ghi trên cùng một dòng được cách nhau một dấu cách.

Ràng buộc:

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm: \(N \le 20\).

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm: \(N \le 2000\).

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm: không có ràng buộc gì thêm.

Output

Dòng thứ nhất ghi một số nguyên dương \(t\) là tổng tiền vé tìm được của tất cả các cách đi, lấy phần dư khi chia cho \(10^9 + 7\).

Example

Input:

5
2 4 1 3 6
2 3
1 3
2 3
1 3
1 1

Output:

8

Note

Có \(2\) cách đi từ nhà ga \(1\) đến nhà ga \(5\):

Từ nhà ga \(1\) đi đến nhà ga \(3\), sau đó từ nhà ga \(3\) đi đến nhà ga \(5\); tổng tiền vé cho cách đi là \(2 + 1 = 3\).

Từ nhà ga \(1\) đi đến nhà ga \(4\), sau đó từ nhà ga \(4\) đi đến nhà ga \(5\); tổng tiền vé cho cách đi là \(2 + 3 = 5\).

Tổng tiền vé cho tất cả các cách đi từ nhà ga \(1\) đến nhà ga \(5\) là \(3 + 5 = 8\).