Problem
Băng nhóm của Fomin bao gồm n nhóm, mỗi nhóm có ai người. Các cuộc tấn công q đã được lên kế hoạch. Cuộc đột kích thứ i sẽ bao gồm chính xác một tên cướp từ mỗi nhóm có số hiệu nằm trong đoạn \([l_i, r_i]\).
Melekhov rất buồn, vì vậy đối với mỗi cuộc đột kích, anh ấy quyết định tính toán số đơn vị có thể có theo modulo
\(10^9 + 7\). Tuy nhiên, Gregory không ngừng suy nghĩ về ý nghĩa của cuộc sống và tìm kiếm sự thật nên không thể tập trung tính toán và nhờ bạn giúp đỡ.
Đầu vào
Dòng đầu tiên chứa số
n (
\(1 <= n <= 10^5\)) – số lượng nhóm trong băng Fomin.
Dòng thứ hai chứa
n số tự nhiên
ai (
\(1 <= a_i < = 10^6\)) – số người trong nhóm thứ
i.
Dòng thứ ba chứa số
q – số lần tấn công.
Sau đây là các dòng
q, mỗi dòng chứa hai số –
li và
ri (
\(1 <= l_i <= r_i <= n\)) – số nhóm tham gia cuộc đột kích thứ
i-.
Dấu ấn
In các số
q, mỗi số trên một dòng riêng biệt – đáp ứng nhiệm vụ.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |