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 10

^{9}+ 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

1 <= k <= 10^5

-10^4 <= arr[i] <= 10^4

Loading...

View Submissions

Console