Piling Papers

문제

Farmer John wrote down $NN$ ($1\le N\le 3001\backslash le\; N\backslash le\; 300$) digits on pieces of paper. For each $i\in [1,N]i\backslash in\; [1,N]$, the $ii$th piece of paper contains digit $a_{i}a\_i$ ($1\le a_i\le 91\; \backslash leq\; a\_i\; \backslash leq\; 9$).

The cows have two favorite integers $AA$ and $BB$ (), and would like you to answer $QQ$ ($1\le Q\le 5\cdot {10}^{4}1\backslash le\; Q\backslash le\; 5\backslash cdot\; 10^4$) queries. For the $ii$th query, the cows will move left to right across papers $l_i\dots r_{i}l\_i\backslash dots\; r\_i$ ($1\le l_i\le r_i\le N1\backslash le\; l\_i\backslash le\; r\_i\backslash le\; N$), maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all $3^{r_i-l_i+1}3^\{r\_i-l\_i+1\}$ ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in $[A,B][A,B]$ inclusive, and output this number modulo ${10}^9+710^9+7$.

입력

The first line contains three space-separated integers $NN$, $AA$, and $BB$.

The second line contains $NN$ space-separated digits $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash dots,\; a\_N$.

The third line contains an integer $QQ$, the number of queries.

The next $QQ$ lines each contain two space-separated integers $l_{i}l\_i$ and $r_{i}r\_i$.

출력

For each query, a single line containing the answer.

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

2
18
34