B. 最大和

单个测试点时间限制：$1$ 秒 单个测试点内存限制：$256$ 兆字节

给定一个长度为 $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\times10^5$），分别表示数组长度和操作次数。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9\le a_i\le 10^9$）。

保证所有测试用例的 $n$ 之和与 $k$ 之和均不超过 $2\times10^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