Alimzhan loves ACM
Alimzhan is desperately trying not to come up with another combinatorics problem. He knows that competitive programmers love arrays and binary numbers. He created a function f[a](m) for a number m (0 ≤ m ≤ 2^n - 1) and an array a[0], a[1], ..., a[n-1].
where b[0], b[1], ..., b[k-1] are indexes of ones in the binary representation of m.
For example, f[a](5) = a[0] + a[2] and f[a](11) = a[0] + a[1] + a[3].
Suddenly, Alimzhan’s inner voice started shouting: "Count number of such m-s so that f[a](m+1) > f[a](m) !!!". To make this problem a little bit more ACM alike Alimzhan asks you to answer to q queries.
You have q pairs of numbers l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1). For each query i, consider an array c[i] = (a[li], a[li+1], ..., a[ri]). Count the number of m (0 ≤ m ≤ 2^(r-l+1) - 1), such that f[c](m + 1) > f[c](m).
Input
The first line contains an integer n (1 ≤ n ≤ 2 * 10^5) – length of an array a.
Second line contains n integers a[0], a[1], ..., a[n-1] (-10^9 ≤ a[i] ≤ 10^9) - elements of an array a.
Third line contains an integer q - the number of queries.
The next q contain pairs of integers l[i], r[i] (0 ≤ l[i] ≤ r[i] ≤ n - 1).
Output
For each query, print one integer - the answer to the query, in separate lines. Print the answer modulo 10^9 + 7.