### 问题描述 给定一个长度为 $n$ 的整数数组 $a$ 以及 $m$ 个查询。 每个查询包含三个整数 $l,r,k$ 表示询问 $l \sim r$ 之间所有元素的 $k$ 次方和。 请对每个查询输出一个答案，答案对 $10^9+7$ 取模。 ### 输入格式 第一行输入两个整数 $n,m$ 其含义如上所述。 第二行输入 $n$ 个整数 $a[1],a[2],...,a[n]$。 接下来 $m$ 行，每行输入三个整数 $l,r,k$ 表示一个查询。 ### 输出格式 输出 $m$ 行，每行一个整数，表示查询的答案对 $10^9+7$ 取模的结果。 ### 样例输入 ```txt 5 3 1 2 3 4 5 1 3 2 2 4 3 3 5 1 ``` ### 样例输出 ```txt 14 99 12 ``` ### 评测数据规模： 对于 $100$% 的评测数据：$ 1 \leq n,m \leq 10^5 $，$ 1 \leq a[i] \leq 100 $，$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq 5 $。