Фермер Джон выписал \(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\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит три разделённых одиночными пробелами целых числа \(N\), \(A\), \(B\).
Вторая строка содержит \(N\) разделённых одиночными пробелами цифр \(a_1, a_2, \dots, a_N\).
Третья строка содержит целое число \(Q\), количество запросов.
Каждая их следующих \(Q\) строк содержит два разделённых пробелами целых числа \(l_i\) и \(r_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого запроса одна строка содержит ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 13 327
1 2 3 4 5
3
1 2
1 3
2 5
|
2
18
34
|