311185: CF1946B. Maximum Sum

B. Maximum Sumtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an array $a$ of $n$ integers.

You perform exactly $k$ operations on it. In one operation, you select any contiguous subarray of the array $a$ (possibly empty) and insert the sum of this subarray anywhere in the array.

Your task is to find the maximum possible sum of the array after $k$ such operations.

As this number can be very large, output the answer modulo $10^9 + 7$.

Reminder: the remainder of a number $x$ modulo $p$ is the smallest non-negative $y$ such that there exists an integer $q$ and $x = p \cdot q + y$.

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2 \cdot 10^5$) — the length of the array $a$ and the number of operations, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the array $a$ itself.

It is guaranteed that the sum of the values of $n$ and $k$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test, output a single integer — the maximum sum of the array that can be obtained after $k$ operations modulo $10^9 + 7$.

ExampleInput

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

Output

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

Note

In the first test case, it is advantageous to take an empty subarray of the array twice and insert the sum of the empty subarray (zero) anywhere, then the sum of the resulting array will be $(-4) + (-7) + 0 + 0 = -11$, modulo $10^9 + 7$ this is $999\,999\,996$.

In the second test case, it is advantageous to take the sum of the entire array three times and place it anywhere in the array, then one of the possible sequences of actions: [$2, 2, 8$] $\rightarrow$ [$2, 2, 8, 12$] $\rightarrow$ [$2, 2, 8, 12, 24$] $\rightarrow$ [$2, 2, 8, 12, 24, 48$], the sum of the final array is $2 + 2 + 8 + 12 + 24 + 48 = 96$.

In the fourth test case, it is advantageous to take a subarray of the array consisting of the first three numbers (i.e. consisting of the numbers $4, -2$ and $8$) and insert its sum at the beginning of the array, thereby obtaining the array [$10, 4, -2, 8, -12, 9$], the sum of this array is $17$.

In the seventh test case, it will always be advantageous for us to take an empty subarray of the array. In this case, the sum of the resulting array will not differ from the sum of the original. The answer will be the sum of the original array, taken modulo — $42$, because $(-6 \cdot (10^9 + 7) + 42 = -6\,000\,000\,000)$.

题目大意：
给定一个包含n个整数的数组a。你将对它执行恰好k次操作。在一次操作中，你可以选择数组a的任意一个连续子数组（可能为空），并将其和插入到数组的任意位置。你的任务是找到经过k次这样的操作后，数组的最大可能和。由于这个数字可能非常大，输出答案模10^9 + 7的余数。

输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数n和k（1≤n, k≤2×10^5）——数组a的长度和操作的数量。
每个测试用例的第二行包含n个整数a1, a2, …, an（-10^9≤ai≤10^9）——数组a本身。
保证所有测试用例的n和k的值之和不超过2×10^5。

输出数据格式：
对于每个测试，输出一个整数——经过k次操作后可以得到的数组的最大和模10^9 + 7的余数。题目大意： 给定一个包含n个整数的数组a。你将对它执行恰好k次操作。在一次操作中，你可以选择数组a的任意一个连续子数组（可能为空），并将其和插入到数组的任意位置。你的任务是找到经过k次这样的操作后，数组的最大可能和。由于这个数字可能非常大，输出答案模10^9 + 7的余数。 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和k（1≤n, k≤2×10^5）——数组a的长度和操作的数量。 每个测试用例的第二行包含n个整数a1, a2, …, an（-10^9≤ai≤10^9）——数组a本身。 保证所有测试用例的n和k的值之和不超过2×10^5。 输出数据格式： 对于每个测试，输出一个整数——经过k次操作后可以得到的数组的最大和模10^9 + 7的余数。