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

где 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 (0 ≤ li ≤ ri ≤ n - 1). Для каждого запроса i рассмотрим массив ci = (ali, ali+1, ..., ari). Вычислите количество таких m (0 ≤ m ≤ 2r-l+1 - 1), что fc(m + 1) > fc(m).

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

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

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

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

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

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

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