题目描述

给定拥有\(n\)个数的序列\(A\)。定义\(f(k)\)表示在序列\(A\)中找出拥有\(k\)个元素的子序列（元素相同但位置不同的算多次），并将它们的积求和。
例如，当\(A=\){\(2,3,4\)}，\(f(2)=26\)。原因如下: 所有的长度为\(2\)的子序列共有3个，分别是{\(2,3\)},{\(2,4\)},{\(3,4\)}，它们的乘积之和为\(2\times3+2\times4+3\times4=26\)。
现在，凉心的Ducati会\(q\)次询问你\(\sum_{l=x}^y\sum_{r=l}^y\sum_{i=l}^{r}f(i)\)的值。这个式子的值等价于如下伪代码片段：

for l=x~y
    for r=l~y
        for i=l~r
            f(i)的和;

由于答案可能过大，请将答案对\(1000000007(10^9+7)\)取模。

输入格式

第一行输入\(n\)和\(q\)，表示序列中元素的个数与询问的次数。
第二行输入\(n\)个数，表示序列\(A\)的\(n\)个元素。
下面输入\(q\)行，每行两个整数\(x\)和\(y\)，表示询问\(\sum_{l=x}^y\sum_{r=l}^y\sum_{i=l}^{r}f(i)\)的值。

输出格式

输出\(q\)行，第\(i\)行为第\(i\)个询问的答案。

输入输出样例

输入

3 2
1 2 3
1 1
2 3

输出

6
34

样例解释

首先，得到\(f(1)=6,f(2)=11,f(3)=6\)。
第一个询问是求\(f(1)\)，即\(6\)。
第二个询问是求\(f(2)+(f(2)+f(3))+f(3)\)，即\(34\)。

数据范围

对于100%的数据，\(1\le n,q\le1000\)，\(1\le a_i≤10^9\)，\(x\le y\)。
Subtask 1(10%): \(x=y\)。
Subtask 2(20%): \(n,q\le5\)。
Subtask 3(20%): \(n,q\le100\)。
Subtask 4(10%): \(a_i≤1000\)。
Subtask 5(40%): 无特殊限制。

贡献者

题面:Ducati
数据，核题:b6e0