종이 쌓기

Farmer John이 종이 $N$장($1\le N\le 300$)에 숫자를 적었다. 각 $i\in [1,N]$에 대해 $i$번째 종이에는 숫자 $a_i$($1 \leq a_i \leq 9$)가 적혀 있다.

소들에게는 좋아하는 정수 $A$와 $B$($1\le A\le B< 10^{18}$)가 있고, 소들은 $Q$개의 질의($1\le Q\le 5\cdot 10^4$)에 답을 얻고자 한다. $i$번째 질의에서 소들은 종이 $l_i$번째부터 $r_i$번째까지($1\le l_i\le r_i\le N$) 왼쪽에서 오른쪽으로 차례로 지나가며, 처음에는 빈 더미를 유지한다. 각 종이마다 더미의 맨 위에 올리거나, 맨 아래에 놓거나, 아무것도 하지 않는다. 과정이 끝나면 더미를 위에서 아래로 읽어 정수를 만든다. 가능한 $3^{r_i-l_i+1}$가지 선택 전부에 대해, 읽은 정수가 $[A,B]$ 구간에 들어가는 경우의 수를 세고, 그 값을 $10^9+7$로 나눈 나머지를 출력한다.

첫째 줄에 세 정수 $N$, $A$, $B$가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 숫자 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어진다.

셋째 줄에 질의의 개수 $Q$가 주어진다.

이어지는 $Q$개의 줄에는 각각 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어진다.

각 질의마다 답을 한 줄에 출력한다.