Nông dân John viết \(N(1 \leq N\leq300)\) chữ số lên một vài mảnh giấy. Với mỗi \(i\in[1,N]\), mảnh giấy thứ \(i\) chứa chữ số \(a_i\) \((1\leq a_i \leq 9)\).

Những con bò có hai số nguyên yêu thích \(A\) và \(B (1\leq A\leq B<10^{18} )\) và muốn bạn trả lời \(Q\) truy vấn \((1\leq Q\leq5*10^4)\). Đối với truy vấn thứ i, đám bò sẽ đi qua các mảnh giấy \(l_i…r_i (1\leq l_i\leq r_i\leq N )\) từ trái sang phải, duy trì một chồng giấy. Đối với mỗi mảnh giấy, chúng sẽ thêm nó vào đầu chồng, vào cuối chồng hoặc không thêm vào. Cuối cùng, chúng sẽ đọc các mảnh giấy trong chồng từ trên xuống dưới, tạo thành một số nguyên. Trên tất cả \(3^{r_i−l_i+1}\) cách để chúng đưa ra lựa chọn, hãy đếm số cách tạo ra số nằm trong đoạn \([A,B]\) in ra số này với \(modulo\) \(10^9+7\).

Input

• Dòng đầu tiên chứa ba số \(N\), \(A\) và \(B\).
• Dòng thứ hai chứa \(a_1,a_2,..,a_N\).
• Dòng thứ ba chứa số \(Q\) - số truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i\) và \(r_i\).

Output

In ra kết quả mỗi truy vấn trên \(1\) dòng.

Scoring

• Subtask \(1\): \(B < 100\)
• Subtask \(2\): \(A=B\)
• Subtask \(3\): Không có điều kiện gì thêm.

Example

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

2
18
34