您有一个由 $$$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 \cdot 10^5$$$) - 分别是数组 $$$a$$$ 的长度和操作数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) - 数组 $$$a$$$ 本身。
保证所有测试用例的 $$$n$$$ 和 $$$k$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试,输出一个整数——$$$k$$$ 运算模 $$$10^9 + 7$$$ 后可以获得的数组的最大和。
示例
输入 #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
输出 #1
999999996 96 896 17 351 716455332 42 2 0 897909241 0 416571966
注意
在第一个测试用例中,最好采用数组的空子数组两次,并在任何地方插入空子数组(零)的总和,然后所得数组的总和将是 $$$(-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$$$。
在第四个测试用例中,最好取由前三个数字组成的数组的子数组(即由数字 $$$4、-2$$$ 和 $$$8$$$ 组成)并将其和插入数组的开头,从而获得数组 [$$$10, 4, -2, 8, -12, 9$$$],该数组的和为$$$17$$$。
在第七个测试用例中,采用数组的空子数组对我们来说总是有利的。在这种情况下,结果数组的总和将与原始数组的总和没有不同。答案将是原始数组的总和,取模 $$$42$$$,因为 $$$(-6 \cdot (10^9 + 7) + 42 = -6\,000\,000\,000)$$$。