B. Максимальная сумма
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ из $$$n$$$ целых чисел.

Вы выполняете ровно $$$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$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных нам выгодно взять пустой подотрезок массива дважды и вставить сумму пустого подотрезка(ноль) куда угодно, тогда сумма полученного массива будет $$$(-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)$$$.