← 返回题目列表

Codeforces · 878/E

E. 黑板上的数字

中文机器翻译题面 查看原题

n 个整数的序列写在黑板上。很快,萨沙就会来到黑板前,开始执行以下操作:设x和y是两个相邻的数字(x在y之前),然后他可以将它们删除并写成x + 2y来代替它们。他将执行这些操作,直到剩下一个数字。萨莎喜欢大数字,并且会得到尽可能大的数字。

Nikita 想在 Sasha 之前到达黑板并擦除一些数字。他有q个选项,在选项i中,他擦除第li个数字左边的所有数字和第ri个数字i右边的所有数字。 e. li-th 和 ri-th 之间(含)的所有数字都保留在黑板上。对于每个选项,他都想知道 Sasha 的最终数字有多大。这个数字可能非常大,因此输出它对 109 + 7 求模。

输入

第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 105) — 黑板上的整数个数和 Nikita 的选项个数。

下一行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 黑板上的序列。

接下来的 q 行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ n),描述 Nikita 的选项。

输出

对于每个选项,输出 Sasha 的结果模 109 + 7。

示例

输入 #1

3 3
1 2 3
1 3
1 2
2 3

输出 #1

17
5
8

输入 #2

3 1
1 2 -3
1 3

输出 #2

1000000006

输入 #3

4 2
1 1 1 -1
1 4
3 4

输出 #3

5
1000000006

注意

在第二个示例中,Nikita 没有删除任何内容。 Sasha 首先擦除数字 1 和 2,写入 5。然后擦除 5 和 -3,得到 -1。 -1 模 109 + 7 为 109 + 6。