511. K-subarray

1

Medium

Samwell tarley needs assistance in finding the maximum sub-array sum. He has requested your help with this task. However, there is a slight twist to the problem. The array will be formed by repeating the original array k times, and you need to find the answer for this modified array. Please note that the answer can be very large, so return the answer modulo 109 + 7. Additionally, the length of the sub-array can be 0, and in that case, the sum is considered to be 0 as well.

Input Format

The first line of input will contain the length of the array and the value of k, separated by a space. The second line will contain the elements of the array, separated by spaces.

Output Format

Output the maximum sub-array sum.

Example

Input

2 3 1 2

Output

9

Constraints

1 <= n <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
Loading...

View Submissions

Console