Numbers on the blackboard

2000ms

524288K

Description:

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 l_i-th number and all numbers to the right of r_i-th number, i. e. all numbers between the l_i-th and the r_i-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 10⁹ + 7.

Input:

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

The next line contains n integers a₁, a₂, ..., a_n ( - 10⁹ ≤ a_i ≤ 10⁹) — the sequence on the blackboard.

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

Output:

For each option output Sasha's result modulo 10⁹ + 7.

Sample Input:

Sample Output:

17
5
8

Sample Input:

3 1
1 2 -3
1 3

Sample Output:

1000000006

Sample Input:

Sample Output:

5
1000000006

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 10⁹ + 7 is 10⁹ + 6.

Informação

Provedor Codeforces

Código CF878E