SAlt

Mathematical Final Boss is getting tired from all his success and decided to start playing with some integer sequences.

After a while, he found a very interesting function which he called $SAlt$. For a sequence of numbers $S = a_1, a_2, \ldots, a_k$, he takes the non-increasing sorted sequence and stars to alternatively add and substract numbers.
Formally if the sorted sequence is $a_{i_1},a_{i_2},\ldots, a_{i_k}$, we have
$SAlt(S) = \sum_{p=1}^{k}(-1)^{(p-1)}\cdot a_{i_p}$.

This is too easy for our Final Boss, so, for a sequence of numbers he now wants to compute the sum of the $SAlt$ values for all its subsets.

Now every morning he takes an integer sequence $A$ with $N$ numbers and $Q$ queries $q_i=(l_i,r_i)$ that ask for the $SAlt$ sum of all subsets of numbers of the substring $A[l_i,r_i]$.

He can do all these computations in less than a second and he is now curious if you can do it too with the help of a modern computer.

Because the numbers can become very large, you have to compute it modulo $10^9 + 7$.

Input data

First line will contain one integer $N$, $1 \leq N \leq 10^5$ - the length of the sequence.
The second line will contain $N$ numbers $(1 \leq A_i \leq 2\cdot 10^5)$ - the elements of the sequence.
The third line contains $Q$, $1 \leq Q \leq 10^5$ - the number of queries.
The following $Q$ lines each have a pair of numbers $l_i,r_i$ denoting the query interval.

Output data

The $i$-th line will represent the answer to the $i$-th query given by the Final Boss.

Constraints and clarifications

• For $20$ points, it is guaranteed that $N\leq20$ and $Q\leq 50$.
• For the other $80$ points, we have $N \leq 10^5$ and $Q \leq 10^5$.

Example

stdin

5
5 4 3 2 1
3
2 3
1 5
2 2

stdout

8
80
4

Explanation

For the first query, we have the substring $4,3$, with the subsets $S_1 = \{4\}, S_2 = \{3\}, S_3 = \{3,4\}$.
We have $SAlt(S_1) = 4$, $SAlt(S_2) = 3$ and $SAlt(S_3) = 4 - 3 = 1$.
The answer for this query is $4+3+1=8$.