和积和III

和积和III

题目描述

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

信息

ID
1014
难度
4
分类
(无)
标签
递交数
3
已通过
1
通过率
33%
被复制
1
上传者