Se tiene un arreglo de ~n~ enteros: ~a = [a_1, a_2, \dots, a_n]~. Definimos el peso -~w(s)~- de una subecuencia ~s~ de ~a~ como el producto de sus elementos.

Un subsecuencia de ~a~ es el arreglo resultante de eliminar varios (posiblemente 0 o todos) elementos de ~a~ (de cualquier lugar de ~a~).

Definimos el costo -~cost(l, r)~- de un rango ~a[l\dots r]~, como la suma de los pesos de todas sus subsecuencias.

Formalmente:

$$\displaystyle cost(l, r) = \displaystyle \sum_{s\subset [l, r]} \left( \prod_{i \in s} a_i\right)$$

Por ejemplo, en el arreglo ~[3, 4, 2]~, ~cost(1, 3) = 3 + 4 + 2 + 3\cdot4 + 3\cdot 2 + 4\cdot2 + 3\cdot 4\cdot 2 = 59~

Usted recibirá ~Q~ consultas. En la ~i~-ésima consulta, recibirá dos enteros ~l_i, r_i~, (~l_i \leq r_i~), y usted debe imprimir el valor de ~cost(l_i, r_i)~. Como este valor puede ser muy grande, de el resultado módulo ~1 000 000 007, (10^9 + 7)~.

Entrada

La primera línea contiene un número entero ~N~, la longitud del arreglo.

La segunda línea contiene ~N~ enteros separados por espacio, (~a_1, a_2, \dots, a_N~, respectivamente). Cada ~a_i \in [1, 10^9]~.

La tercera línea contiene un número entero ~Q~, el número de consultas a realizar.

Cada una de las siguientes ~Q~ líneas, contiene dos enteros separados por espacio ~l~ y ~r~, respectivamente, (~1 \le l < r \le N~).

Salida

Debe contener exactamente ~Q~ líneas, la ~i~-ésima de ellas conteniendo la respuesta a la ~i~-ésima consulta.

Restricciones

Primera Subtarea (25 puntos)

• ~Q = 1, l_1 = 1, r_1 = N~
• ~1 \le N \le 16~

Segunda Subtarea (35 puntos)

• La suma de las longitudes de los rangos de cada consulta no excede ~10^5~.

Tercera Subtarea (40 puntos)

• ~1 \le N \le 10^5~
• ~1 \le Q \le 10^5~

Ejemplo de Entrada

5
9 5 8 8 10
3
2 2
3 3
3 4

Ejemplo de Salida

5
8
80