B'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 . Each test consists of several test cases. The first line contains a single integer t ( 1 <= t <= 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 <= n, k <= 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 <= a_i <= 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 . For each test, output a single integer -- the maximum sum of the array that can be obtained after k operations modulo 10^9 + 7 . 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 a'...