题目描述

给定一个长度为 $n$ 的整数数组 $a$。

你需要对其进行恰好 $k$ 次操作。每次操作，你可以选择数组 $a$ 的任意一个连续子数组（可以为空），并将该子数组的和插入到数组的任意位置。

你的任务是求出经过 $k$ 次这样的操作后，数组的最大可能和。

由于答案可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

提示：一个数 $x$ 模 $p$ 的余数是最小的非负整数 $y$，使得存在整数 $q$ 满足 $x = p \cdot q + y$。

输入格式

每组测试数据包含若干组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2 \times 10^5$），分别表示数组 $a$ 的长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$），表示数组 $a$。

保证所有测试用例中 $n$ 和 $k$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，输出一个整数，表示经过 $k$ 次操作后数组可能获得的最大和，对 $10^9 + 7$ 取模。

说明/提示

在第一个测试用例中，最优做法是两次选择空子数组并插入其和（零），最终数组的和为 $(-4) + (-7) + 0 + 0 = -11$，模 $10^9 + 7$ 后为 $999\,999\,996$。

在第二个测试用例中，最优做法是三次选择整个数组的和并插入，操作过程如下：[ 2, 2, 8 \rightarrow 2, 2, 8, 12 \rightarrow 2, 2, 8, 12, 24 \rightarrow 2, 2, 8, 12, 24, 48 ]，最终数组的和为 $2 + 2 + 8 + 12 + 24 + 48 = 96$。

在第四个测试用例中，最优做法是选择前 $3$ 个数组成的子数组（即 $4, -2, 8$），将其和插入到数组开头，得到新数组 [ 10, 4, -2, 8, -12, 9 ]，其和为 $17$。

在第七个测试用例中，最优做法始终是选择空子数组。此时最终数组的和与原数组相同。答案为原数组的和对 $42$ 取模，因为 $(-6 \cdot (10^9 + 7) + 42 = -6\,000\,000\,000)$。

由 ChatGPT 4.1 翻译

样例

12
2 2
-4 -7
3 3
2 2 8
1 7
7
5 1
4 -2 8 -12 9
7 4
8 14 -9 6 0 -1 3
7 100
5 3 -8 12 -5 -9 3
6 1000
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000
2 1
1000000000 8
5 4
0 0 0 0 0
6 10
48973 757292 58277 -38574 27475 999984
7 1
-1000 1000 -1000 1000 -1000 1000 -1000
10 10050
408293874 -3498597 7374783 295774930 -48574034 26623784 498754833 -294875830 283045804 85938045

999999996
96
896
17
351
716455332
42
2
0
897909241
0
416571966