Фермер Джон виписав \(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\dots 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\).

Формат вихідних даних

Для кожного запиту один рядок містить відповідь.

Приклад вхідних даних

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

Приклад вихідних даних

2
18
34

Для першого запиту існує дев’ять способів, якими Бессі може складати папери під час читання інтервалу ~[1, 2]

• Бесі може ігнорувати цифру \(1\) потім ігнорувати \(2\), і отримати \(0\).
• Бесі може ігнорувати \(1\) потім додати \(2\) у вершину стека і отримати \(2\).
• Бесі може ігнорувати \(1\) потім додати \(2\) у дно стека, і отримати \(2\).
• Бесі може додати \(1\) у вершину стека потім ігнорувати \(2\), отримати \(1\).
• Бесі може додати \(1\) у вершину стека потім додати \(2\) у вершину стека, отримати \(21\).
• Бесі може додати \(1\) у вершину стека потім додати \(2\) у дно стека, отримати \(12\).
• Бесі може додати \(1\) у дно стека потім ігнорувати \(2\), отримати \(1\).
• Бесі може додати \(1\) у дно стека потім додати \(2\) у вершину стека, отримати \(21\).
• Бесі може додати \(1\) у дно стека потім додати \(2\) у дно стека, отримати \(12\).

Вийшло тільки \(2\) тільки 2 способи отримати число між \(13\) і \(327\) (це число \(21\)), тому відповідь \(2\).

ОЦІНЮВАННЯ:

• У тестах 2-3: \(B<100\)
• У тестах 4-5: \(A=B\)
• У тестах 6-13: Немає додаткових обмежень.