SP19416 POTIONS - Potions Class

斯内普给出 $n$ 个数 $(a_1, a_2, a_3, \ldots, a_n)$ 和 $q$ 个查询。每个查询包括四个整数：**w, x, y, z**。每个查询的结果可通过以下公式计算： $$ \sum_{i=y}^{z} (a_{x+i} \cdot w^i) \mod (10^9 + 7) $$ 请帮助哈利回答这些问题，以免他被惩罚入狱禁闭。

输入的第一行为一个整数 $T$，表示总共有多少组测试用例。接下来是 $T$ 组测试用例数据。 每组测试用例的第一行包括两个整数 $n$ 和 $q$。 每组测试用例的第二行提供 $n$ 个整数 $(a_1, a_2, a_3, \ldots, a_n)$。 随后的 $q$ 行，每行包含四个整数 **w, x, y, z**。

对于每个测试用例，按照查询顺序输出结果。注意，结果可能会很大，所以请返回结果对 $10^9 + 7$ 取模的值。

- $1 \le T \le 10$ - $1 \le n, q \le 10^5$ - 对于每个 $y \le i \le z$，都有 $1 \le x + i \le n$ - $0 \le a_i \le 10^9$，对于 $1 \le i \le n$ - $1 \le w \le 10^6$ - $0 \le y \le z$ **本翻译由 AI 自动生成**