Numbers on the blackboard
Contest: Codeforces Round 443 (Div. 1)
Difficulty rating: 3300
Tags: combinatorics, dp

A sequence of n integers is written on a blackboard. Soon Sasha will come to the blackboard and start the following actions: let x and y be two adjacent numbers (x before y), then he can remove them and write x + 2y instead of them. He will perform these operations until one number is left. Sasha likes big numbers and will get the biggest possible number.

Nikita wants to get to the blackboard before Sasha and erase some of the numbers. He has q options, in the option i he erases all numbers to the left of the li-th number and all numbers to the right of ri-th number, i. e. all numbers between the li-th and the ri-th, inclusive, remain on the blackboard. For each of the options he wants to know how big Sasha's final number is going to be. This number can be very big, so output it modulo 109 + 7.

Input format:
The first line contains two integers n and q (1 ≤ n, q ≤ 105) — the number of integers on the blackboard and the number of Nikita's options.

The next line contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence on the blackboard.

Each of the next q lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing Nikita's options.

Output format:
For each option output Sasha's result modulo 109 + 7.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the second sample Nikita doesn't erase anything. Sasha first erases the numbers 1 and 2 and writes 5. Then he erases 5 and -3 and gets -1. -1 modulo 109 + 7 is 109 + 6.

Example input:
3 3
1 2 3
1 3
1 2
2 3

Example output:
17
5
8

Example input:
3 1
1 2 -3
1 3

Example output:
1000000006

Editorial:
Let's find a strategy for Sasha. His result can be represented in the form $$\sum_{i=1}^{n} a_i 2^{k_i}$$, where k1 = 0, 1 ≤ ki ≤ ki - 1 + 1 for i > 1.
For all ki satisfying these conditions he can obtain such result. We prove this by induction. For n = 1 is't obvious. Let n > 1. Find the greatest i such that ki = 1. It always exists cause k2 = 1. By the induction hypothesis we can get k1, k2... ki - 1 and ki - 1, ki + 1 - 1... kn - 1. Do this and merge them with the last move.
Now we describe the strategy. Let the last number be negative. Then Sasha wants to minimize kn. He always can use kn = 1. If tha last number is non-negative, he can use kn = kn - 1 + 1. In this case, Sasha first merges the last two numbers. Thus, the sequence ki consists of several blocks, in each of which ki + 1 = ki + 1, and each of the blocks except the first begins with 1.
Now we need to answer queries. We will do it offline. On the step i add the number ai and and answer all queries with r = i. We will support the blocks for the query [1, i].
What happens when we add a number? If it's negative, it simply forms a separate block. Otherwise it becomes the end of some block. It is easy to see that the new block is the union of several old blocks.
How to answer queries? [l, r] is the union of some blocks and a suffix of another block. We can see that this is the partition into blocks for our query.
How to do it fast? We will store the boundaries of blocks to do binary search on them and find the block in which the l lies. We need to store the results for each block and prefix sums of these results. Also we need to find sums $$\sum_{j=1}^{i} a_j 2^j$$ to find out results for suffixes.
Each step is processed in $${\mathcal {O}}(\log n)$$ except for merging blocks. But we create at most one block on each step, so amortized time of each step is $${\mathcal {O}}(\log n)$$.
Also in this problem we need to be careful with overflows. Although we need to find the result modulo some prime, in some places the sign is important. We can use that if |y| is more than maximum ai, then x + 2y is also big and have the same sign.
BONUS: solve this problem online.
БОНУС: solve it in O(nα(n)).