Problem
Geng Fomin terdiri daripada kumpulan n, setiap satunya mempunyai ai orang. serbuan q telah dirancang. Serbuan ke-iakan merangkumi tepat seorang perompak daripada setiap kumpulan yang bilangannya terletak dalam segmen \([l_i, r_i]\).
Melekhov sedih, jadi untuk setiap serbuan dia memutuskan untuk mengira bilangan unit modulo
\(10^9 + 7\). Walau bagaimanapun, Gregory sentiasa memikirkan tentang erti kehidupan dan mencari kebenaran, jadi dia tidak dapat menumpukan perhatian pada pengiraan dan meminta bantuan anda.
Input
Baris pertama mengandungi nombor
n (
\(1 <= n <= 10^5\)) – bilangan kumpulan dalam kumpulan Fomin.
Baris kedua mengandungi
n nombor asli
ai (
\(1 <= a_i < = 10^6\)) – bilangan orang dalam kumpulan
i-th.
Baris ketiga mengandungi nombor
q – bilangan serbuan.
Berikut ialah baris
q, setiap satu mengandungi dua nombor –
li dan
ri (
\(1 <= l_i <= r_i <= n\)) – bilangan kumpulan yang mengambil bahagian dalam serbuan
i-.
Cetakan
Cetak nombor
q, setiap satu pada baris berasingan – tindak balas terhadap tugasan.
Contoh
| # |
Input |
Output |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |