Arrays and Queries

Problem Description

Given an integer $n$ and an array $a$ of $n$ integers. The process of constructing the array $b$ is defined as follows.

Initially, the array $b$ is empty. The process is carried out in $n$ consecutive rounds. In the $i$-th round, the new array $b$ is defined as the concatenation of the previous version of the array $b$, the element $a_i$, and again the previous version of the array .

Formally, in each $i$-th round, the array $b$ is updated according to the rule:

$b := b + [a_i] + b$,

where the symbol «$+$» denotes the concatenation of arrays, and $[a_i]$ is an array consisting of a single element $a_i$.

After the construction of the array $b$ is completed, it is necessary to process $q$ queries. Each query is defined by a pair of integers $(l, r)$. For each query, it is required to find the sum of the elements of the array $b$ from position $l$ to position $r$ inclusive modulo $$.

Input format

In the first line, an integer $n$ $(1 \le n \le 60)$ is given --- the number of elements in the array $a$.

In the second line, $n$ integers are given $a_1, a_2, \ldots, a_n$ $$ --- the elements of the array .

In the third line, an integer $q$ $(1 \le q \le 2 \cdot 10^5)$ is given --- the number of queries.

In the following $q$ lines, pairs of integers $l$ and $r$ are given $(1 \le l \le r \le 2^n - 1)$.

Output format

For each query, output a single number --- the sum of the elements of the array $b$ on the segment $[l, r]$ modulo $10^9 + 7$. Output each answer on a separate line.

Scoring

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

9
13
9
0
11
9