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ứ isẽ có chính xác một kẻ lừa đảo từ mỗi nhóm có số hiệu nằm trong phân đ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 là một số n (\(1 <= n <= 10^5\)) – số lượng các nhóm trong băng nhóm của Fomin.
Dòng thứ hai chứa n số tự nhiên ai (\(1 <= a_i <= 2\) ) – số người trong nhóm thứ i-.
Dòng thứ ba chứa số q – số lượng các cuộc 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ố lượng nhóm tham gia cuộc đột kích thứ i-.
Đầu ra
Xuất 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 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |