Competitions

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 fa(m) for a number m (0m2n - 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 (0lirin - 1). For each query i, consider an array ci = (ali, ali+1, ..., ari). Count the number of m (0m2r-l+1 - 1), such that fc(m + 1) > fc(m).

Input

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

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

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

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

Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
1 2 2 6 3
3
0 4
2 3
3 4

Output example #1
26
3
2

Source KBTU Open, Spring Kazakhstan, Alma-Ata, May 30, Problem E