CF878E.Numbers on the blackboard

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 + 2_y_ 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 109 + 7.

黑板上写有一串长度为 $n$ 的整数序列。很快，萨沙（Sasha）将来到黑板前并执行如下操作：设 $x$ 和 $y$ 是两个相邻的数（$x$ 在 $y$ 左侧），他可以将它们移除，并在其位置写上 $x + 2y$。他将持续执行该操作，直到黑板上仅剩一个数为止。萨沙喜欢大数，因此他会采取操作顺序使得最终得到的数尽可能大。

尼基塔（Nikita）希望在萨沙之前到达黑板，并擦除其中一些数字。他有 $q$ 种方案；在第 $i$ 种方案中，他擦除第 $l_i$ 个数左侧的所有数字以及第 $r_i$ 个数右侧的所有数字，即仅保留第 $l_i$ 个到第 $r_i$ 个（含端点）之间的所有数字。对于每种方案，他想知道萨沙最终能得到的最大数是多少。该数可能非常大，因此请输出其对 $10^9 + 7$ 取模的结果。

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 _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — 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.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$）—— 分别表示黑板上整数的个数以及尼基塔的选择次数。

第二行包含 $n$ 个整数 $a_1,\ a_2,\ \dots,\ a_n$（$-10^9 \leq a_i \leq 10^9$）—— 表示黑板上的序列。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述尼基塔的每次选择。

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

对每个选项，输出 Sasha 的结果对 $10^9 + 7$ 取模的值。

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.

在第二个样例中，尼基塔不擦除任何数。萨沙首先擦除数字 1 和 2，并写下 5；然后他擦除 5 和 $-3$，得到 $-1$。$-1 \bmod (10^9 + 7)$ 的结果为 $10^9 + 6$。