Алимжан любит ACM
Алимжан отчаянно пытается решить очередную комбинаторную задачу. Он знает, что программисты любят массивы и двоичные числа. Он создал функцию f[a](m) для числа m (0 ≤ m ≤ 2^n - 1) и массива a[0], a[1], ..., a[n-1].
где b[0], b[1], ..., b[k-1] индексы единиц в двоичном представлении числа m.
Например, f[a](5) = a[0] + a[2] и f[a](11) = a[0] + a[1] + a[3].
Внезапно внутренний голос Алимжана закричал: "Сосчитайте количество таких m - ок, чтобы f[a](m+1) > f[a](m) !!!". Чтобы сделать эту проблему более похожей на ACM, Алимжан просит Вас ответить на q запросов.
Вам даны q пар чисел l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1). Для каждого запроса i рассмотрим массив c[i] = (a[li], a[li+1], ..., a[ri]). Вычислите количество таких m (0 ≤ m ≤ 2^(r-l+1) - 1), что f[c](m + 1) > f[c](m).
Входные данные
Первая строка содержит целое число n (1 ≤ n ≤ 2 * 10^5) - длину массива a.
Вторая строка содержит n целых чисел a[0], a[1], ..., a[n-1] (-10^9 ≤ a[i] ≤ 10^9) - элементы массива a.
Третья строка содержит число q - количество запросов.
Каждая из следующих q строк содержит пары целых чисел l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1).
Выходные данные
Для каждого запроса выведите в отдельной строке одно целое число - ответ на него. Выведите ответ по модулю 10^9 + 7.