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 [li,ri]. ;
Melekhov está triste, así que para cada incursión decidió calcular el número de unidades posibles módulo
109+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<=105) – el número de grupos en la banda de Fomin.
La segunda línea contiene n números naturales ai (1<=ai<=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<=li<=ri<=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 |