P16646 [GKS 2018 #C] Kickstart Alarm

Shil 每天早上起床都非常困难，因此他决定买一个功能强大的闹钟来 Kickstart 他的一天。这个闹钟被称为 Kickstart Alarm。它预配置了 $K$ 个强有力的唤醒呼叫。在睡觉前，用户用参数数组 $A_1, A_2, \dots, A_N$ 对闹钟进行编程。早上，闹钟会响 $K$ 次，第 $i$ 次唤醒呼叫的强度为 $\text{POWER}_i$。 为了计算 $\text{POWER}_i$，闹钟会生成参数数组的所有连续子数组，并计算所有连续子数组的第 $i$ 次指数幂之和。子数组 $A_j, A_{j+1}, \dots, A_k$ 的第 $i$ 次指数幂定义为 $A_j \times 1^i + A_{j+1} \times 2^i + A_{j+2} \times 3^i + \dots + A_k \times (k - j + 1)^i$。因此，$\text{POWER}_i$ 就是参数数组所有连续子数组的第 $i$ 次指数幂之和。 例如，若 $i = 2$，且 $A = [1, 4, 2]$，则第 $i$ 次指数幂的计算如下： * $[1]$ 的第 2 次指数幂 $= 1 \times 1^2 = 1$ * $[4]$ 的第 2 次指数幂 $= 4 \times 1^2 = 4$ * $[2]$ 的第 2 次指数幂 $= 2 \times 1^2 = 2$ * $[1, 4]$ 的第 2 次指数幂 $= 1 \times 1^2 + 4 \times 2^2 = 17$ * $[4, 2]$ 的第 2 次指数幂 $= 4 \times 1^2 + 2 \times 2^2 = 12$ * $[1, 4, 2]$ 的第 2 次指数幂 $= 1 \times 1^2 + 4 \times 2^2 + 2 \times 3^2 = 35$ 总和为 $71$。 今晚，Shil 第一次使用他的 Kickstart Alarm。因此，他非常担心闹钟早上可能发出的声音。它可能会吵醒邻居，甚至更糟，可能会吵醒整个星球！然而，对他来说计算每次唤醒呼叫的强度相当困难。给定 $K$ 和参数数组 $A_1, A_2, \dots, A_N$，你能通过计算每次唤醒呼叫的强度之和 $\text{POWER}_1 + \text{POWER}_2 + \dots + \text{POWER}_K$ 来帮助他吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行九个整数组成：$N$、$K$、$x_1$、$y_1$、$C$、$D$、$E_1$、$E_2$ 和 $F$。其中 $N$ 是数组 $A$ 的长度，$K$ 是唤醒呼叫的次数。其余的值是用于生成数组 $A$ 元素的参数，生成方式如下。 对于 $i = 2$ 到 $N$，使用以下递推式生成 $x_i$ 和 $y_i$： * $x_i = (C \times x_{i-1} + D \times y_{i-1} + E_1) \bmod F$。 * $y_i = (D \times x_{i-1} + C \times y_{i-1} + E_2) \bmod F$。 对于所有 $i = 1$ 到 $N$，定义 $A_i = (x_i + y_i) \bmod F$。

对于每个测试用例，输出一行，格式为 `Case #x: POWER`，其中 $x$ 是测试用例编号（从 $1$ 开始），`POWER` 是对于 $i = 1$ 到 $K$ 的 $\text{POWER}_i$ 之和。由于 `POWER` 可能非常大，请输出它对 $1000000007$（即 $10^9 + 7$）取模的结果。

在样例 #1 中，参数数组为 $[3, 2]$。所有连续子数组为 $[3]$、$[2]$、$[3, 2]$。 对于 $i = 1$： * $[3]$ 的第 1 次指数幂 $= 3 \times 1^1 = 3$ * $[2]$ 的第 1 次指数幂 $= 2 \times 1^1 = 2$ * $[3, 2]$ 的第 1 次指数幂 $= 3 + 2 \times 2^1 = 7$ 所以 $\text{POWER}_1 = 12$。 对于 $i = 2$： * $[3]$ 的第 2 次指数幂 $= 3 \times 1^2 = 3$ * $[2]$ 的第 2 次指数幂 $= 2 \times 1^2 = 2$ * $[3, 2]$ 的第 2 次指数幂 $= 3 + 2 \times 2^2 = 11$ 所以 $\text{POWER}_2 = 16$。 对于 $i = 3$： * $[3]$ 的第 3 次指数幂 $= 3 \times 1^3 = 3$ * $[2]$ 的第 3 次指数幂 $= 2 \times 1^3 = 2$ * $[3, 2]$ 的第 3 次指数幂 $= 3 + 2 \times 2^3 = 19$ 所以 $\text{POWER}_3 = 24$。 ### 限制条件 $1 \le T \le 100$。 $1 \le x_1 \le 10^5$。 $1 \le y_1 \le 10^5$。 $1 \le C \le 10^5$。 $1 \le D \le 10^5$。 $1 \le E_1 \le 10^5$。 $1 \le E_2 \le 10^5$。 $1 \le F \le 10^5$。 **小数据集（测试集 1 – 可见）** $1 \le N \le 100$。 $1 \le K \le 20$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 10^6$。 $1 \le K \le 10^4$。 翻译由 DeepSeek V4 Pro 完成