Problem D. 第 k 次部分和

时间限制：3s

空间限制：256MB

题目背景

纳西妲研究完了斐波那契数列，又开始对前缀和感兴趣了。她了解到前缀和数组可以加速求数组的部分和，这就让她思考到，如果对前缀和数组继续一直求前缀和，又该如何求部分和呢？

题目描述

对一个长度为 \(n\) 的数组 \(A = [a_1, a_2, a_3, ..., a_n]\) 进行多次求前缀和的操作

设 \(S_{k,i}\) 表示第 \(k\) 次前缀和的第 \(i\) 项，它的定义如下：

• \(S_{0,i}\) 为原数组，即 \(S_{0,1} = a_1\),\(S_{0,2} = a_2\), ..., \(S_{0, n} = a_n\).
• \(S_{1,i}\) 为原数组的前缀和数组，即\(S_{1,1} = a_1\), \(S_{1,2} = a_1 + a_2\), ..., \(S_{1,n} = a_1 + a_2 + ... + a_n\).
• \(S_{k,i} = S_{k-1,1} + S_{k-1, 2} + ... + S_{k-1,i}\). (\(k \ge 1\))

现在给定数组 \(A\) 及其长度 \(n\)，询问多组 \(k, l, r\)，输出 \(S_{k,l} + S_{k,l+1} + ... + S_{k,r-1} + S_{k, r}\) 的值。

输入格式

第一行两个整数 \(n\) 和 \(T\) ，代表数组长度和询问组数；

第二行 \(n\) 个整数，用空格隔开，代表数组 \(A\);

接下来 \(T\) 每行三个整数 \(k, l, r\), 用空格隔开，代表每组询问。

输出格式

输出 \(T\) 行，每行一个整数，代表 \(S_{k,l} + S_{k,l+1} + ... + S_{k,r-1} + S_{k, r}\) 的结果；由于结果可能很大，请输出结果对 \(1e9 + 7\) 取模的值。

样例输入1

4 3
1 2 3 4
0 1 4
1 2 3
3 4 4

样例输出1

10
9
35

样例1解释

\(S_{0 \sim 3, 1 \sim 4}\) 的值如下：

\(S_0 = [1,2,3,4]\)

\(S_1 = [1,1+2,1+2+3,1+2+3+4] = [1,3,6,10]\)

\(S_2 = [1,1+3,1+3+6,1+3+6+10] = [1,4,10,20]\)

\(S_3 = [1,1+4,1+4+10,1+4+10+20] = [1,5,15,35]\)

样例输入2

见sum2.in

样例输出2

见sum2.out

样例输入3

见sum3.in

样例输出3

见sum3.out

数据范围与限制

测试点编号	约定	测试点分值
\(1 \sim 2\)	\(T = 1, k_1 = 0\)	每个测试点5分
\(3 \sim 4\)	\(k_i = 0\)	每个测试点5分
\(5 \sim 8\)	\(1 \le n \le 100, 0 \le k_i \le 9\)	每个测试点5分
\(9 \sim 12\)	\(1 \le n \le 1000, 0 \le k_i \le 999\)	每个测试点5分
\(13 \sim 20\)	无特殊约定	每个测试点5分

对于所有测试点， \(1 \le n \le 10^5\), \(1 \le T \le 500\),\(0 \le a_i \le 10^9\), \(0 \le k_i \le 10^6\), \(1 \le l_i \le r_i \le n\).