# 2021 KBTU Open, Spring Kazakhstan, Alma-Ata, May 30

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

for a number _{a}(m)**m** (**0** ≤ **m** ≤ `2`

- ^{n}**1**) and an array `a`

, _{0}`a`

, ..., _{1}`a`

._{n-1}

where `b`

, _{0}`b`

, ..., _{1}`b`

are indexes of ones in the binary representation of _{k-1}**m**.

For example, `f`

= _{a}(5)`a`

+ _{0}`a`

and _{2}`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`

!!!". To make this problem a little bit more ACM alike Alimzhan asks you to answer to _{a}(m)**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`

). Count the number of _{ri}**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`

) – length of an array ^{5}**a**.

Second line contains **n** integers `a`

, _{0}`a`

, ..., _{1}`a`

(_{n-1}`-10`

≤ ^{9}`a`

≤ _{i}`10`

) - elements of an array ^{9}**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**.

5 1 2 2 6 3 3 0 4 2 3 3 4

26 3 2