Problem
La pandilla de Fomin consta de n grupos, cada uno de los cuales tiene ai personas. Se planean redadas q. La redada i-ésima incluirá exactamente un ladrón de cada grupo cuyo número se encuentra en el segmento \([l_i, r_i]\).
Melekhov está triste, así que para cada incursión decidió calcular el número de unidades posibles módulo
\(10^9 + 7\). Sin embargo, Gregory está constantemente pensando en el significado de la vida y buscando la verdad, por lo que no puede concentrarse en los cálculos y te pide ayuda.
Entrada
La primera línea contiene el número
n (
\(1 <= n <= 10^5\)) – el número de grupos en la banda de Fomin.
La segunda línea contiene
n números naturales
ai (
\(1 <= a_i < = 10^6\)) – el número de personas en el grupo
i-th.
La tercera línea contiene el número
q – número de allanamientos.
Las siguientes son líneas
q, cada una de las cuales contiene dos números –
li y
ri (
\(1 <= l_i <= r_i <= n\)) – número de grupos que participan en
i-th raid.
Impresión
Imprima números
q, cada uno en una línea separada – respuesta a la tarea.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |