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 fa(m) for a number m (0 ≤ m ≤ 2n - 1) and an array a0, a1, ..., an-1.

where b0, b1, ..., bk-1 are indexes of ones in the binary representation of m.

For example, fa(5) = a0 + a2 and fa(11) = a0 + a1 + a3.

Suddenly, Alimzhan’s inner voice started shouting: "Count number of such m-s so that fa(m+1) > fa(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 li, ri (0 ≤ li ≤ ri ≤ n - 1). For each query i, consider an array ci = (ali, ali+1, ..., ari). Count the number of m (0 ≤ m ≤ 2r-l+1 - 1), such that fc(m + 1) > fc(m).

Input

The first line contains an integer n (1 ≤ n ≤ 2 * 105) – length of an array a.

Second line contains n integers a0, a1, ..., an-1 (-109 ≤ ai ≤ 109) - elements of an array a.

Third line contains an integer q - the number of queries.

The next q contain pairs of integers li, ri (0 ≤ li ≤ ri ≤ n - 1).

Output

For each query, print one integer - the answer to the query, in separate lines. Print the answer modulo 109 + 7.