Module: tiền tố

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