问题描述

给定一个长度为 $n$ 的整数数组 $a$ 以及 $m$ 每个查询包含三个整数 $l,r,k$ 表示询问 $l∼r$ 之间所有元素的 $k$ 次方和。

请对每个查询输出一个答案，答案对 $10^9 + 7$ 取模。

输入格式

第一行输入两个整数 $n,m$ 其含义如上所述。

第二行输入 $n$ 个整数 $a_1,a_2 \ldots a_n$

接下来 $m$ 行，每行输入三个整数 $l,r,k$ 表示一个查询。

输出格式

输出 $m$ 行，每行一个整数，表示查询的答案对 $10^9+7$ 取模的结果。

样例输入

5 3
1 2 3 4 5
1 3 2
2 4 3
3 5 1

样例输出

14
99
12

限制与约定

对于$20 \%$的数据，保证 $k=1 \ ,1 \le n \le 100 \ ,1 \le m \le 100 \ ,1 \le a_i \le 100 $

对于$50 \%$ 的数据，保证 $ 1\le k \le 5 , 1 \le n \le 10^5 \ ,1 \le m \le 100 \ ,1 \le a_i \le 100$

另外对于10%的数据，保证$k=1 \ ,1 \le n \le 10^5 \ ,1 \le m \le 10^5 \ ,1 \le a_i \le 10^9 $

对于$100 \%$ 的数据，保证 $ 1\le k \le 5 , 1 \le n \le 10^5 \ ,1 \le m \le 10^5 \ ,1 \le a_i \le 100 , l \le r \le n $

• 时间限制: $1 s$
• 空间限制: $256 MB$