Given an integer array arr and an integer k, modify the array by repeating it k times.
For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.
As the answer can be very large, return the answer modulo 10^9 + 7.
Example 1:
Input: arr = [1,2], k = 3
Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5
Output: 2
Example 3:
Input: arr = [-1,-2], k = 7
Output: 0
Constraints:
1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4
class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        def kadane(ls, n):
            max_sum_so_far = ls[0]
            current_sum = ls[0]
            for i in range(1, n):
                current_sum = max(current_sum + ls[i], ls[i])
                max_sum_so_far = max(max_sum_so_far, current_sum)
            return max_sum_so_far
        n = len(arr)
        first_max_sum = kadane(arr, n)
        if k <= 1:
            return first_max_sum
        arr_sum = sum(arr)
        arr.extend(arr)
        next_max_sum = kadane(arr, 2*n)
        
        if arr_sum < 0:
            return max(next_max_sum, 0)
        
        if arr_sum >=0 and next_max_sum > arr_sum:
            return (next_max_sum + (k-2)*arr_sum) %(10**9 + 7)
        # if arr_sum >
        
        return max(first_max_sum, 0)
        

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        def kadane(ls, n):
            max_sum_so_far = ls[0]
            current_sum = ls[0]
            for i in range(1, n):
                current_sum = max(current_sum + ls[i], ls[i])
                max_sum_so_far = max(max_sum_so_far, current_sum)
            return max_sum_so_far
        n = len(arr)
        first_max_sum = kadane(arr, n)
        if k <= 1:
            return first_max_sum
        arr_sum = sum(arr)
        arr.extend(arr)
        next_max_sum = kadane(arr, 2*n)
        
        if arr_sum < 0:
            return max(next_max_sum, 0)
        
        if arr_sum >=0 and next_max_sum > arr_sum:
            return (next_max_sum + (k-2)*arr_sum) %(10**9 + 7)
        # if arr_sum >
        
        return max(first_max_sum, 0)
        
