eolymp
Змагання

2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

Алимжан любит ACM

Алимжан отчаянно пытается решить очередную комбинаторную задачу. Он знает, что программисты любят массивы и двоичные числа. Он создал функцию fa(m) для числа m (0m2n - 1) и массива a0, a1, ..., an-1.

prb10642.gif

где b0, b1, ..., bk-1 индексы единиц в двоичном представлении числа m.

Например, fa(5) = a0 + a2 и fa(11) = a0 + a1 + a3.

Внезапно внутренний голос Алимжана закричал: "Сосчитайте количество таких m - ок, чтобы fa(m+1) > fa(m) !!!". Чтобы сделать эту проблему более похожей на ACM, Алимжан просит Вас ответить на q запросов.

Вам даны q пар чисел li, ri (0lirin - 1). Для каждого запроса i рассмотрим массив ci = (ali, ali+1, ..., ari). Вычислите количество таких m (0m2r-l+1 - 1), что fc(m + 1) > fc(m).

Входные данные

Первая строка содержит целое число n (1n2 * 105) - длину массива a.

Вторая строка содержит n целых чисел a0, a1, ..., an-1 (-109ai109) - элементы массива a.

Третья строка содержит число q - количество запросов.

Каждая из следующих q строк содержит пары целых чисел li, ri (0lirin - 1).

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число - ответ на него. Выведите ответ по модулю 109 + 7.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
1 2 2 6 3
3
0 4
2 3
3 4
Вихідні дані #1
26
3
2
Джерело 2021 KBTU Open, Весна Казахстан, Алма-Ата, 30 мая, Задача E