У вас есть массив \(a\) из \(n\) целых чисел.
Вы выполняете ровно \(k\) операций над ним. В одной операции вы выбираете любой непрерывный подотрезок массива \(a\) (возможно, пустой) и вставляете сумму этого подотрезка в любое место массива.
Ваша задача — найти максимально возможную сумму массива после \(k\) таких операций.
Поскольку это число может быть очень большим, выведите ответ по модулю \(10^9 + 7\).
Напомним, что остаток от числа \(x\) по модулю \(p\) — это наименьшее неотрицательное \(y\), такое что существует целое число \(q\) и \(x = p \cdot q + y\).
Примечание
В первом наборе входных нам выгодно взять пустой подотрезок массива дважды и вставить сумму пустого подотрезка(ноль) куда угодно, тогда сумма полученного массива будет \((-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)\).