Xếp Chồng Giấy

Nông dân John viết $N$ chữ số trên các tờ giấy. Các con bò có hai số nguyên yêu thích $A$ và $B$, và cần trả lời $Q$ truy vấn. Mỗi truy vấn cho khoảng $[l,r]$, các con bò xử lý từng tờ giấy từ trái sang phải, với mỗi tờ có 3 lựa chọn:

• Đặt lên đỉnh chồng giấy
• Đặt xuống đáy chồng giấy
• Bỏ qua tờ giấy

Sau đó đọc số từ đỉnh xuống đáy. Hãy đếm số cách chọn (trong $3^{r-l+1}$ cách) tạo ra số nằm trong khoảng $[A,B]$ (modulo ${10}^9+7$).

Dữ liệu vào

• Dòng 1: Ba số nguyên $N$, $A$, $B$ ($1\le N\le 300$, $1\le A\le B<{10}^{18}$).
• Dòng 2: $N$ chữ số $a_1,a_2,\dots ,a_N$ ($1\le a_i\le 9$).
• Dòng 3: Số nguyên $Q$ ($1\le Q\le 5·{10}^4$).
• $Q$ dòng tiếp theo: Hai số nguyên $l_i$, $r_i$ ($1\le l_i\le r_i\le N$).

Dữ liệu ra

Với mỗi truy vấn, in số cách hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 300$
• $1\le A\le B<{10}^{18}$
• $1\le a_i\le 9$
• $1\le Q\le 5·{10}^4$

Ví dụ