L. SAlt
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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, \cdots 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},\cdots 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

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

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

Scoring
  • 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
Input
5
5 4 3 2 1
3
2 3
1 5
2 2
Output
8
80
4
Note

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