Alimzhan loves ACM#10642
Alimzhan is desperately trying to solve another combinatorics problem. He knows that competitive programmers love arrays and binary numbers. He created a function f_a(m) for a number (0 \le m \le 2^n - 1) and an array a_0, a_1, \ldots, a_{n-1}.
where b_0, b_1, \ldots, b_{k-1} are indexes of ones in the binary representation of .
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 the number of such '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 queries.
You have pairs of numbers l_i, r_i (0 \le l_i \le r_i \le n - 1). For each query , consider an array c_i = (a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}). Count the number of (0 \le m \le 2^{r-l+1} - 1), such that f_c(m + 1) > f_c(m).
The first line contains an integer (1 \le n \le 2 \cdot 10^5) – length of an array .
Second line contains integers a_0, a_1, \ldots, a_{n-1} (-10^9 \le a_i \le 10^9) - elements of an array .
Third line contains an integer - the number of queries.
The next lines contain pairs of integers l_i, r_i (0 \le l_i \le r_i \le n - 1).
For each query, print one integer - the answer to the query, in separate lines. Print the answer modulo 10^9 + 7.
Example 1