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。