Giảng viên viết $N(1\le N\le 300)$ chữ số vào các khối lập phương $($mỗi khối chứa $1$ chữ số trong đoạn $[1,9])$.

Thầy rất thích $2$ số $A$ và $B$. Thầy muốn hỏi Tú Anh $Q$ câu hỏi $(1\le Q\le 5\ast {10}^4)$.

Với câu hỏi thứ $i$, Tú Anh nhận được 2 chỉ số $l$ và $r$ $(1\le l_i\le r_i\le N)$.

Tú Anh có thể thao tác lần lượt với các khối từ $l$ đến $r$ như sau, giả sử bạn ấy sẽ xếp các khối thành một cột, với mỗi khối, bạn ấy có thể bỏ vào trên cùng hoặc dưới cùng của cột, hoặc sẽ không bỏ vào. Sau khi thao tác xong các khối, bạn ấy sẽ đọc các số từ các khối theo thứ tự từ trên xuống dưới, tạo thành một số nguyên.

Câu hỏi dành cho Tú Anh là đếm số cách tạo thành một số nằm trong đoạn $[A,B]$, in ra kết quả theo modulo ${10}^9+7$.

Input

Dòng đầu tiên chứa $3$ số $N,A,B$.

Dòng thứ $2$ chứa $N$ chữ số được ghi vào các khối từ $1$ đến $N$.

Dòng thứ $3$ chứa $Q$ là số lượng câu hỏi.

$Q$ dòng tiếp theo mỗi dòng chứa $2$ số $l_i$ và $r_i$.

Output

Với mỗi câu hỏi, in ra câu trả lời trên một dòng.

Constraints

$25\mathrm{\%}$ số test có $B\le 100$.

$25\mathrm{\%}$ số test có $A=B$.

Sample Input

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

Sample Output

2
18
34

Giải thích: Với câu hỏi số $1$, có $9$ cách mà Tú Anh có thể thao tác với các khối từ $1$ đến $2$.

• Bỏ qua $1$, bỏ qua $2$, nhận được số $0$.
• Bỏ qua $1$, thêm $2$ vào trên cùng, nhận được số $2$.
• Bỏ qua $1$, thêm $2$ vào dưới cùng, nhận được số $2$.
• Thêm $1$ vào trên cùng, bỏ qua $2$, nhận được số $1$.
• Thêm $1$ vào dưới cùng, bỏ qua $2$, nhận được số $1$.
• Thêm $1$ vào trên cùng, thêm $2$ vào trên cùng, nhận được số $21$.
• Thêm $1$ vào trên cùng, thêm $2$ vào dưới cùng, nhận được số $12$.
• Thêm $1$ vào dưới cùng, thêm $2$ vào trên cùng, nhận được số $21$.
• Thêm $1$ vào dưới cùng, thêm $2$ vào dưới cùng, nhận được số $12$.

Chỉ có $2$ cách nhận được số nằm trong đoạn $[13,327]$.