Алімжан любить 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.