Массивы и Запросы

Описание задачи

Дано целое число $n$ и массив $a$ из $n$ целых чисел. Процесс построения массива $b$ определяется следующим образом.

Изначально массив $b$ пуст. Процесс выполняется в $n$ последовательных раундах. На $i$-ом раунде новый массив $b$ определяется как конкатенация предыдущей версии массива $b$, элемента $a_i$ и снова предыдущей версии массива .

Формально, на каждом $i$-ом раунде массив $b$ обновляется согласно правилу:

$b := b + [a_i] + b$,

где символ «$+$» обозначает конкатенацию массивов, а $[a_i]$ — это массив, состоящий из одного элемента $a_i$.

После завершения построения массива $b$ необходимо обработать $q$ запросов. Каждый запрос определяется парой целых чисел $(l, r)$. Для каждого запроса требуется найти сумму элементов массива $b$ с позиции $l$ по позицию $r$ включительно по модулю $$.

Формат ввода

В первой строке дано целое число $n$ $(1 \le n \le 60)$ — количество элементов в массиве $a$.

Во второй строке даны $n$ целых числа $a_1, a_2, \ldots, a_n$ $$ — элементы массива .

В третьей строке дано целое число $q$ $(1 \le q \le 2 \cdot 10^5)$ — количество запросов.

В следующих $q$ строках даны пары целых чисел $l$ и $r$ $(1 \le l \le r \le 2^n - 1)$.

Формат вывода

Для каждого запроса выведите одно число — сумму элементов массива $b$ на отрезке $[l, r]$ по модулю $10^9 + 7$. Выводите каждый ответ на отдельной строке.

Система оценки

3
2 0 5
6
1 4
1 7
3 5
6 6
3 7
4 7

9
13
9
0
11
9