题目内容

塔塔君有一长度为$n$的输出数组，他需要对这个数组进行$k$次插入操作，每次操作可以在当前数组任意位置插入一个数字，这个数字是当前数组的某个连续子数组（可以为空）中元素之和。塔塔君希望经过$k$次操作之后，最终数组总和最大。

输入描述

第一行包含一个整数$T$($1≤T≤10000$)，表示总共有$T$组样例

接下来每组样例包含两行：

第一行包含两个整数$n$和$k$($1≤n,k≤10000$)

$n$表示初始数字长度,$k$表示总计需要进行$k$次插入操作

第二行包含$n$整数$a_1,a_2,...,a_n$($-10^9≤a_i≤10^9,1≤i≤n$)

输出描述

包含$T$行

每一行包含一个整数，即经过$k$次插入操作后，可能的最大数组总和，因为数组总和肯能很大，输出总和对$10^9+7$取模作为答案

样例1

输入

3
3 3
2 2 8
2 2
-4 -7
7 2
8 14 -9 6 0 -1 3

输出

96
999999996
87