# 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.