410283: GYM103999 L 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, \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$$$.

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.

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

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

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

8
80
4

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