Problem
La pandilla de Fomin consta de n grupos, cada uno de los cuales tiene ai personas. Se planean redadas q. La incursión ith tendrá exactamente un pícaro 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 es un 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 <= 2\) ) – número de personas en i-ésimo grupo.
La tercera línea contiene el número q – número de redadas.
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 la i-th raid.
Salida
Salida
q números, cada uno en una línea separada – respuesta a la tarea.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |