题目描述

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$）取模的结果。

2
2 3 1 2 1 2 1 1 9
10 10 10001 10002 10003 10004
10005 10006 89273

Case #1: 52
Case #2: 739786670

提示

在样例 #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 完成