题目描述

给定拥有$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