El Granjero Juan escribió ~N~ dígitos en pedazos de papel. Para cada ~i\in [1,N]~, el i-ésimo pedazo de papel contiene el dígito ~a_i~.

Las vacas tienen dos enteros favoritos ~A~ y ~B~, y les gustaría su respuesta a ~Q~ pregunta. Para la pregunta i-ésima, las vacas moveran de izquierda a derecha los papeles ~l_i...r_i~, manteniendo una pila inicialmente de papeles. Para cada papel, ellas lo sumaran al tope de la pila , a la parte inferior de la pila, o ninguno. Al final, ellas leeran los papeles en la pila de arriba hacia abajo, formando un entero. Sobre todas las ~3^{r_i-l_i+1}~ maneras para que las vacas de hacer las elecciones durante este proceso, cuente el número de maneras en que las vacas lear un entero en ~[A,B]~ inclusive, y dé como salida este número modulo ~10^9+7~.

Entrada

• La primera línea contiene tres enteros separados por espacios ~N, A,~ y ~B~.
• La segunda línea contiene ~N~ enteros separados por espacios ~a_1,a_2,...,a_N~.
• La tercera línea contiene un entero ~Q~, el número de preguntas.
• Las siguientes ~Q~ líneas contienen dos enteros separados por espacio ~l_i~ y ~r_i~.

Salida

Para cada pregunta, una sola línea conteniendo la respuesta.

Restricciones

• ~1 \leq N \leq 300~
• ~1 \leq a_i \leq 9~
• ~1 \leq A \leq B < 10^{18}~
• ~1 \leq Q \leq 5 \cdot 10^4~

Ejemplo de Entrada

5 13 327
1 2 3 4 5
3
1 2
1 3
2 5

Ejemplo de Salida

2
18
34

Para la primera pregunta, hay nueve maneras en que Bessie puede apilar papeles cuando leyendo el intervalo ~[1,2]~:

• Bessie puede ingorar 1 luego ignorar 2, obtniendo 0.
• Bessie puede ignorar 1 luego añadir 2 al tope de la pila, obteniendo 2.
• Bessie puede ignorar 1 luego añadir 2 a la parte inferior de la pila, obteniendo 2.
• Bessie puede añadir 1 al tope de la pila luego ignorar 2, obteniendo 1.
• Bessie can añadir 1 al tope de la pila luego añadir 2 a la parte superior de la pila, obteniendo 21.
• Bessie puede añadir 1 a la parte superior de la pila, luego añadir 2 en la parte inferior de la pila, obteniendo 12.
• Bessie puede añadir 1 a la parte inferior de la pila, luego ignorar 2, obteniendo 1.
• Bessie puede añadir 1 a la parte inferior de la pila, luego añadir 2 a la parte superior de la pila, obteniendo 21.
• Bessie puede añadir 1 a la parte inferior de la pila, luego añadir 2 en la parte inferior de la pila, obteniendo getting 12.

Solamente 2 maneras que dan 21 produciendo un número entre 13 y 327, entonces la respuesta es 2.

USACO 2023 February Contest, Gold Problem 3. Piling Papers.