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

Difficulty: interview

Starter code:

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        

Solutions:
class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        oneArrSum = sum(arr)
        twoArr = arr + arr
        
        def findMaxSub(array):
            if len(array) == 1:
                return array[0]
            
            cur = 0
            small = 0
            ret = -999999
            for i in array:
                cur += i
                small = cur if cur < small else small
                ret = cur - small if cur - small > ret else ret
           
            return 0 if ret < 0 else ret
        
        if not arr:
            return 0
        if k == 1:
            return findMaxSub(arr)
        
        ret = findMaxSub(twoArr)
        if oneArrSum > 0 and k > 2:
            ret += (k-2)*oneArrSum
        return ret % (10**9 + 7)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if not arr or k == 0: return 0
        N = 10 ** 9 + 7
        n = len(arr)
        accu = [0] * (n+1)
        for i in range(1,n+1):
            accu[i] = accu[i - 1] + arr[i - 1]
        s = accu[-1]
        accuMaxL = max(accu)
        accuMaxR = s - min(accu)
        a0, sMax = 0, 0
        for a in accu:
            a0 = min(a,a0)
            sMax = max(sMax, a - a0)
        if sMax <= 0:
            return 0
        elif k == 1:
            return sMax
        elif s <= 0:
            ans = max(sMax, accuMaxR + accuMaxL)
            return ans
        elif (sMax - accuMaxL - accuMaxR)/k > s:
            return sMax
        else:
            ans = accuMaxR + accuMaxL % N
            for i in range(k - 2):
                ans = (ans + s) % N
            return ans

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        def getMaximumSum(subArr, t):
            subArrT = subArr.copy()
            for i in range(t-1):
                subArrT.extend(subArr) 
            nS = len(subArrT)
            maxSum = 0
            rSum = 0
            for i in range(nS):
                if ((rSum+subArrT[i]) < 0):
                    rSum = 0
                    continue
                else:
                    rSum += subArrT[i]
                    if (rSum > maxSum):
                        maxSum = rSum
            return maxSum
        def getHeadSum(subArr):
            headSum = 0
            nS = len(subArr)
            rSum = 0
            for i in range(nS):
                rSum += subArr[i]
                if (rSum > headSum):
                    headSum = rSum
            return headSum
        headSum = getHeadSum(arr)
        tailSum = getHeadSum(arr[::-1])
        sumArr  = sum(arr)
        
        result = 0
        if (sumArr > 0):
            if (k == 1):
                result = getMaximumSum(arr,1)
            elif (k == 2):
                result = tailSum + headSum
            else:
                result = tailSum + (k-2)*sumArr + headSum
        else:
            if (k > 1):
                if ((headSum + tailSum) > result):
                    result = headSum+tailSum
                    
            if (getMaximumSum(arr,1) > result):
                result = getMaximumSum(arr,1)
            
        return result%(10**9+7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        MAX_INT = 10**9+7
        
        def kadane(arr):
            cur, res = 0, 0
            for v in arr:
                cur = max(v, cur+v)
                res = max(res, cur)
            return res
        
        if k == 1: return kadane(arr)
        else:
            s = sum(arr)
            if s <= 0: return kadane(arr*2)
            else: return (kadane(arr) + (k-1)*s)%MAX_INT

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        m = 10**9 + 7
        
        #kadane helper algo
        def kadane(numbers):
            best = 0 
            curr = 0
            for x in numbers:
                curr = max(0, curr+x)
                best = max(best, curr)
            return best
        
        #stupid approach
        #a = arr*k
        #return max_subarray(a) % m
        
        tot = sum(arr)
        
        if not k:
            return 0
        elif k == 1:
            return kadane(arr) % m
        else:
            return ((k-2)*max(tot,0)+kadane(arr*2)) % m


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        sumarr=sum(arr)
        maxsum=0
        currentsum=0
        for i in range(len(arr)):
            currentsum+=arr[i]
            if(currentsum<0):
                currentsum=0
            maxsum=max(maxsum,currentsum)
        if(sumarr>0):
            if(sumarr*k>maxsum):
                maxsum=sumarr*k
        maxprefixsum=0
        currentsum=0
        for i in range(len(arr)):
            currentsum+=arr[i]
            maxprefixsum=max(maxprefixsum,currentsum)
        maxsufixsum=0
        currentsum=0
        for i in range(len(arr)-1,-1,-1):
            currentsum+=arr[i]
            maxsufixsum=max(maxsufixsum,currentsum)
        if(k>=2):
            maxsum=max(maxsum,maxsufixsum+maxprefixsum)
        if(sumarr>0):
            maxsum=max(sumarr*(k-2)+maxsufixsum+maxprefixsum,maxsum)
        return maxsum%1000000007
            
            
        


class Solution:
    def findMaxSubarray(arr):
        counter = 0
        best = 0
        for a in arr:
            counter += a
            if counter < 0:
                counter = 0
            else:
                best = max(best, counter)
        return best
    
    def maxFromLeft(arr):
        max_from_left = 0
        sum_from_left = 0
        for a in arr:
            sum_from_left += a
            max_from_left = max(max_from_left, sum_from_left)
        return max_from_left
    
    def maxFromRight(arr):
        max_from_right = 0
        sum_from_right = 0
        for a in reversed(arr):
            sum_from_right += a
            max_from_right = max(max_from_right, sum_from_right)
        return max_from_right
    
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        no_reps = Solution.findMaxSubarray(arr)
        if k == 1:
            return no_reps
        
        arr_sum = sum(arr)
        best_from_left = Solution.maxFromLeft(arr)
        best_from_right = Solution.maxFromRight(arr)
        
        right_and_left = best_from_right + best_from_left
        
        right_and_k_and_left = best_from_right + (k - 2) * arr_sum + best_from_left
        
        res = max(no_reps, right_and_left, right_and_k_and_left)
        
        return res % (10 ** 9 + 7)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        def kadane(arr):
            res, curr = float('-inf'), 0
            for a in arr:
                curr = max(curr+a, a)
                res = max(res, curr)
                
            return res
        
        if k==1: return kadane(arr)
        one_sum = sum(arr)
        if one_sum<0: return max(0, kadane(arr*2))
        return (one_sum*(k-2)+kadane(2*arr))%(10**9+7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        def kadane(lst):
            max_sub = local = 0
            for n in lst:
                max_sub = max(max_sub, local := max(local + n, n))    
            return max_sub
        if k==1 or sum(arr) <= 0:
            return kadane(arr * min(2, k))
        else:
            m = 10**9+7
            return ((kadane(arr) + (k-1)*sum(arr)) % m)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        # dp = [0 for i in range(2*n)]
        # dp[0] = arr[0]
        # ans = dp[0]
        # dp = arr[0]
        # ans = dp
        # sums = sum(arr)
        # begin, maxbegin = 0, 0
        # end, maxend = 0, 0
        # for i in range(1, n * min(2, k)):
        #     cur = arr[i % n]
        #     if dp + cur >= cur:
        #         dp = dp+cur
        #         end = i
        #     else:
        #         dp = cur
        #         begin, end = i, i
        #     if dp > ans:
        #         ans = dp
        #         maxbegin = begin
        #         maxend = i
        # if k == 1:
        #     return ans if ans > 0 else 0
        # if ans < 0:
        #     return 0
        # if maxend % n < maxbegin or maxend < n:
        #     return ans  % (10**9+7)
        # else:
        #     return (ans + sums*(k-2)) % (10**9+7)
        
        
        
        sums = sum(arr)
        dp = 0
        ans = -float('inf')
        for i in range(n * min(2, k)):
            cur = arr[i % n]
            dp = max(dp+cur, cur)
            ans = max(dp, ans)
        return max(0, ans, ans + sums* max(k-2, 0)) % (10**9+7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        mod = 10 ** 9 + 7
        n = len(arr)
        ls = [0 for _ in range(n)]
        rs = [0 for _ in range(n)]
        
        for i in range(n):
            ls[i] = arr[i] + (ls[i-1] if i > 0 else 0)
        for i in range(n-1, -1, -1):
            rs[i] = arr[i] + (rs[i+1] if i < n-1 else 0)
        
        ms = 0
        minls = 0
        for i in range(n):
            minls = min(minls, ls[i])
            ms = max(ms, ls[i]-minls)
        
        mls = max(ls)
        mrs = max(rs)
        ss = sum(arr)
        
        if k == 1:
            return ms
        else:
            if ss < 0:
                return max(ms, mls + mrs) % mod
            else:
                return max(ms, mls + mrs + (k-2) * ss) % mod
        
        
        
        
        
        
        
    
        
        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        now, m, ans = 0, 0, 0
            
        for i in range(n):
            now += arr[i]
            m = min(m, now)
            ans = max(ans, now-m)
        
        if k==1:
            return ans%(10**9+7)
        
        now, pref_M = 0, 0
        
        for i in range(n):
            now += arr[i]
            pref_M = max(pref_M, now)
        
        now, suf_M = 0, 0
        
        for i in range(n-1, -1, -1):
            now += arr[i]
            suf_M = max(suf_M, now)
        
        ans = max(ans, pref_M+suf_M+max(0, sum(arr))*(k-2))
        return ans%(10**9+7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if sorted(arr)[0] >= 0:
            return sum(arr)*k %(10**9+7)
        if sorted(arr)[-1] <= 0:
            return 0
        # temp1, temp2 = 0,0
        if k > 1:
            arr = arr + [max(0,sum(arr)*(k-2))] + arr
        temp, res = 0,0
        for i in range(len(arr)):
            temp += arr[i]
            res = max(res, temp)
            if temp < 0:
                temp = 0
        return res %(10**9+7)

MOD = 1000000007
class Solution:
    def kConcatenationMaxSum(self, arr, k):
        min_pre_sum = 0
        pre_sum = 0
        max_pre_sum, max_suf_sum, max_win_sum = 0, 0, 0
        n = len(arr)
        for i in range(n):
            pre_sum += arr[i]
            max_win_sum = max(max_win_sum, pre_sum - min_pre_sum)
            if i == n - 1:
                max_suf_sum = pre_sum - min_pre_sum
            min_pre_sum = min(min_pre_sum, pre_sum)
            max_pre_sum = max(max_pre_sum, pre_sum)
        if k == 1:
            return max_win_sum
        if pre_sum > 0:
            return max(max_win_sum, max_pre_sum + max_suf_sum + (k - 2) * pre_sum) % MOD
        else:
            return max(max_win_sum, max_pre_sum + max_suf_sum) % MOD

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        def findMaxSum(arr):
            num_sum = 0
            dp = arr[0]
            max_num = arr[0]
            for i in range(1, len(arr)):
                num = arr[i]
                dp = max(dp + num, num)
                max_num = max(max_num, dp)
            return max_num if max_num >= 0 else 0
        
        if k == 0:
            return 0
        elif k == 1:
            return findMaxSum(arr)
        elif k == 2 or sum(arr) < 0:
            return findMaxSum(arr + arr)
        else:
            return (sum(arr) * (k - 2) + findMaxSum(arr + arr))%(10**9 + 7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        mod=1000000007
        fms,sms,msf,meh=0,0,0,0
        for i in range(3):
            for num in arr:
                meh = max(0, (meh+num))
                msf = max(msf, meh)
            if i==0:
                fms = msf
            elif i==1:
                sms = msf
        diff = msf - sms
        print(fms,sms,msf,diff)
        return (sms+diff * (k - 2))%1000000007

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if len(arr) == 0:
            return 0
        
        mod = int(10**9)+7
        v = arr[:]
        pre = [0]
        suf = [0]
        ans = msuf = mpre = 0
        
        for x in arr:
            if k>1: v.append(x)
            ans += x
            pre.append(pre[-1]+x)
            mpre= max(mpre, pre[-1])
            
        for x in arr[::-1]:
            suf.append(suf[-1]+x)
            msuf = max(msuf, suf[-1])
        
        if ans > 0 and k >= 2:
            return (((k-2)*ans)%mod + msuf + mpre)%mod
        
        maxi = 0
        for x in v:
            maxi = max(0, maxi+x)
            ans = max(ans, maxi)
        
        return ans%mod
            
        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        # dp = [0 for i in range(2*n)]
        # dp[0] = arr[0]
        # ans = dp[0]
        dp = arr[0]
        ans = dp
        sums = sum(arr)
        begin, maxbegin = 0, 0
        end, maxend = 0, 0
        for i in range(1, n * min(2, k)):
            cur = arr[i % n]
            if dp + cur >= cur:
                dp = dp+cur
                end = i
            else:
                dp = cur
                begin, end = i, i
            if dp > ans:
                ans = dp
                maxbegin = begin
                maxend = i
        if k == 1:
            return ans if ans > 0 else 0
        if ans < 0:
            return 0
        if maxend % n < maxbegin or maxend < n:
            return ans  % (10**9+7)
        else:
            return (ans + sums*(k-2)) % (10**9+7)


class Solution:  
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        def kadane(nums):
            local_max = nums[0]
            ans = local_max
            for i in range(1,len(nums)):
                local_max = max(nums[i],local_max+nums[i])
                if (ans<local_max): ans = local_max
            return ans if ans>0 else 0
        normal = kadane(arr)
        if k==1: return normal
        tot = sum(arr)
        a = []
        for i in range(2):
            for j in range(n):
                a.append(arr[j])
        mod = 10**9+7
        temp = kadane(a)
        tot = max(0,tot)
        return max(normal,temp,tot*(k-2)+temp)%mod

from typing import List


def get_max(arr: List[int]) -> int:

    mx_running = mx_total = 0

    for n in arr:
        mx_running = n + max(0, mx_running)
        mx_total = max(mx_total, mx_running)

    return mx_total


def get_repeated_max(arr: List[int],
                     k: int,
                     p: int) -> int:

    mx_1 = get_max(arr)
    if k == 1:
        return mx_1 % p
    else:
        mx_2 = get_max(arr + arr)
        if mx_1 > mx_2:
            return mx_1 % p
        else:
            return mx_2 + max(sum(arr) * (k - 2), 0) % p


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        return get_repeated_max(arr, k, int(1e9 + 7))


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if k == 1:
            temp = arr
        else:
            temp = arr + arr
        
        cum = [0]*(len(temp)+1)
        for i in range(1, len(temp)+1):
            cum[i] = cum[i-1] + temp[i-1]
        
        cur = 0
        res = 0
        for c in cum:
            cur = min(cur, c)
            res = max(res, c - cur)
        
        MOD = 10**9 + 7
        if k == 1:
            return res % MOD
        s = sum(arr)
        if res > 2*s > 0:
            return (res + (k-2)*s) % MOD
        elif s > 0:
            return k*s % MOD
        else:
            return res % MOD

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)

        lsum, max_lsum, min_lsum, max_sum, sum, max_rsum, rsum = 0, 0, 0, 0, 0, 0, 0
        for i in range(n):
            lsum+= arr[i]
            max_lsum = max(lsum, max_lsum) # FOR END
            min_lsum = min(lsum, min_lsum) # FOR START
            
            sum += arr[i]
            sum = max(0, sum)
            max_sum = max(sum, max_sum)
            
            rsum += arr[n-1-i]
            max_rsum = max(rsum, max_rsum)
            
        if lsum < 0:
            return max(max_sum,  max_rsum + max_lsum)
        
        if k == 1:
            return max_sum
        
        mod = 10 ** 9 + 7
        return max(lsum * k, lsum * (k -2) + max_rsum + max_lsum) % mod
            
        
#[2,-5,1,0,-2,-2,2] [2,-5,1,0,-2,-2,2] [2,-5,1,0,-2,-2,2] [2,-5,1,0,-2,-2,2]
        
        
        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if not arr or k == 0:
            return 0
        max_sub_arr, total = self.get_max_subarr(arr, 0, len(arr))
        res = 0
        l = self.get_left_max(arr)
        r = self.get_right_max(arr)
        if k == 1:
            return max_sub_arr
        pos = 0
        if k > 3:
            pos = (l+r) + (k-2) * total
            
        return max(total*k, max_sub_arr, (l+r), pos) % (10**9 + 7)
        
    def get_right_max(self, arr):
        res = 0
        cur = 0
        i = len(arr) - 1
        while i >= 0:
            cur += arr[i]
            res = max(cur, res)
            i -= 1
        return res
    
    def get_left_max(self, arr):
        res = 0
        cur = 0
        i = 0
        while i < len(arr):
            cur += arr[i]
            res = max(cur, res)
            i += 1
        return res
        
    def get_max_subarr(self, nums, i, j):
        cur = 0
        res = 0
        total = 0
        for it in range(i, j):
            total += nums[it]
            if nums[it] >= 0:
                cur += nums[it]
                res = max(cur, res)
            else:
                cur = max(cur+nums[it], 0)
        return res, total

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        s=sum(arr)
        def kadane(arr):
            
            cur=m=arr[0]
            for i in range(1,len(arr)):
                cur=max(arr[i],cur+arr[i])
                m=max(cur,m)
            return m
        if not arr:
            return 0
        if k==1:
            return max(0,kadane(arr)%(10**9+7))
        else:
            return max(0, (k - 2) * max(s, 0) + kadane(arr + arr)) % (10 ** 9 + 7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        MOD = 1000000000 + 7
        
        def findMaxSubarray(mat: List[int]) -> int:
            maxSum = 0
            currSum = 0
            
            for i in mat:
                currSum = max(currSum+i, i)
                maxSum = max(maxSum, currSum)
            return maxSum
        
        a = arr.copy()
        if k == 1:
            return findMaxSubarray(a)
        
        a.extend(arr)
        subMax = findMaxSubarray(a)
        
        total = 0
        for n in arr:
            total += n
        
        if total > 0:
            return (subMax + (k-2)*total) % MOD
        else:
            return subMax % MOD


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        len_arr = len(arr)
        curr_max = global_max = 0

        for i in range(len_arr if k == 1 else len_arr * 2):
            n = arr[i % len_arr]
            curr_max = max(n, curr_max + n)
            global_max = max(global_max, curr_max)

        return (global_max + ((k - 2) * max(0, sum(arr)) if k > 1 else 0)) % (10 ** 9 + 7)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        l = len(arr)
        if l == 0:
            return 0
        frontview, backview, sumfront, sumback = [0] * l, [0] * l, [0] * l, [0] * l
        frontview[0], backview[-1], sumfront[0], sumback[-1] = max(0, arr[0]), max(0, arr[-1]), arr[0], arr[-1]
        
        for i in range(1, l):
            frontview[i] = max(0, frontview[i-1] + arr[i])
            backview[l-1-i] = max(0, backview[l-i] + arr[l-1-i])
            sumfront[i] = sumfront[i-1] + arr[i]
            sumback[l-1-i] = sumback[l-i] + arr[l-1-i]
            
        sum_arr = sum(arr)
        base = 10 ** 9 + 7
        
        
        if k == 1:
            return max(frontview) % base
        elif sum_arr <= 0:
            result1 = max(max(frontview), frontview[-1] + backview[0]) % base
            result2 = max(sumfront) + max(sumback)
            print((result1, result2))
            return max(result1, result2) % base
        else:
            result1 = max(max(frontview), frontview[-1] + backview[0])
            result2 = sum_arr * (k - 2) + max(sumfront) + max(sumback)
            if result1 < result2:
                return result2 % base
            else:
                return result1 % base
            
            


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        current = arr[0]
        glob    = arr[0]
        
        for i in range(1, len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
                
        print((current, glob))
        if k==1:
            return glob if glob > 0 else 0
        
        prevCurrent = current
        prevGlob    = glob
        
        for i in range(len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
        
        if prevGlob == glob or k==2:
            return glob if glob > 0 else 0
        
        afterCurrent = current
        afterGlob    = glob
        
        for i in range(len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
                
                
        glob += (glob - afterGlob) * (k-3)
        
        return glob % 1000000007 if glob > 0 else 0
            
            


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        n = len(arr)
        def get_in_arry_max_sum():
            cur = 0
            max_val = 0
            for i in range(n):
                cur = max(0, cur) + arr[i]
                max_val = max(max_val, cur)
            return max_val
        
        max_suffix = list(itertools.accumulate(arr))
        max_suffix = [0 if i > 0 and max_suffix[i-1] == 0 else max(0, max_suffix[i]) for i in range(n)]
        max_prefix = list(itertools.accumulate(arr[::-1]))
        max_prefix = [0 if i > 0 and max_prefix[i-1] == 0 else max(0, max_prefix[i]) for i in range(n)][::-1]
        
        mp = max(max_prefix)
        ms = max(max_suffix)
        # print(max_prefix)
        # print(max_suffix)
        in_arry_max_sum = get_in_arry_max_sum()
        if k == 1:
            return in_arry_max_sum
        if k == 2:
            return max(mp + ms, in_arry_max_sum)

        total = sum(arr)
        return max(in_arry_max_sum, mp + ms + (k-2) * max(0, total)) % (10**9+7)
        


class Solution:

    def kConcatenationMaxSum(self, arr: List[int], k: int, mod = 10 ** 9 + 7) -> int:
        def Kadane(arr, res = 0, cur = 0):
            for num in arr:
                cur = max(num, num + cur)
                res = max(res, cur)
            return res
        return ((k - 2) * max(sum(arr), 0) + Kadane(arr * 2)) % mod if k > 1 else Kadane(arr) % mod

class Solution:
  def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
    # https://en.wikipedia.org/wiki/Maximum_subarray_problem
    # Key:
    # Kadane(arr * 2) is always >= Kadane(arr)
    # Kadane(arr * 2) will always cross the boundary if sum(arr) > 0
    # if Kadane(arr * 2) does not cross the boundary, then Kadane(arr * 2) == Kadane(arr)
    def Kadane(arr):
      # Kadane: status machine
      ans, cur = 0, 0
      for num in arr:
        cur = max(cur + num, num)
        ans = max(ans, cur)
      return ans
    return (((k - 2) * max(sum(arr), 0) + Kadane(arr * 2)) if k > 1 else Kadane(arr)) % (10 ** 9 + 7)

class Solution:
    def kConcatenationMaxSum(self, A: List[int], k: int) -> int:
        if all(a <= 0 for a in A):
            return 0
        total = sum(A)
        N = len(A)
        startingAt, endingAt = [[-sys.maxsize]*N for _ in range(2)]
        bestStart = bestEnd = -sys.maxsize
        MOD = 10**9 + 7
        for i in range(N):
            startingAt[N-1-i] = A[N-1-i] + (startingAt[N-i] if N-i < N and startingAt[N-i] > 0 else 0)
            endingAt[i] = A[i] + (endingAt[i-1] if i-1 >= 0 and endingAt[i-1] > 0 else 0)
            bestStart, bestEnd = max(bestStart, startingAt[N-1-i]), max(bestEnd, endingAt[i])
        if k == 1:
            return bestStart
        
        return max(bestStart,max(0,(endingAt[N-1]) + max(0,total*(k-2)) + max(0,startingAt[0]))) % MOD

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if not arr : return 0
        mod = 10**9+7
        def Kadane(arr):
            sum_till_now = 0
            max_sum = 0
            for i in range(len(arr)):
                sum_till_now += arr[i]
                sum_till_now = max(sum_till_now,arr[i])
                max_sum = max(max_sum,sum_till_now)
            return max_sum
        return ((k - 2) * max(sum(arr), 0) + Kadane(arr * 2)) % mod if k > 1 else Kadane(arr) % mod



class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        numPos, numNeg = 0,0
        
        for num in arr:
            if num >= 0:
                numPos += 1
            else:
                numNeg += 1
        
        if numPos == len(arr):
            return sum(arr)*k
        
        if numNeg == len(arr):
            return 0
        
        # Check for 2* arr
        arrTwo = arr*2
        for i in range(1, len(arrTwo)):
            if arrTwo[i - 1] > 0: 
                arrTwo[i] +=arrTwo[i - 1]
                
        # Check for 3*arr
        arrThree = arr*3
        for i in range(1, len(arrThree)):
            if arrThree[i - 1] > 0: 
                arrThree[i] +=arrThree[i - 1]
        
        arrDiff = max(arrThree) - max(arrTwo)
        
        
        return (max(arrTwo) + (k-2)*arrDiff) % (10**9 + 7)
        
            
        
       
        



class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        numPos, numNeg = 0,0
        
        for num in arr:
            if num >= 0:
                numPos += 1
            else:
                numNeg += 1
        
        if numPos == len(arr):
            return sum(arr)*k
        
        if numNeg == len(arr):
            return 0
        
        # Check for 2* arr
        arrTwo = arr*2
        for i in range(1, len(arrTwo)):
            if arrTwo[i - 1] > 0: 
                arrTwo[i] +=arrTwo[i - 1]
                
        # Check for 3*arr
        arrThree = arr*3
        for i in range(1, len(arrThree)):
            if arrThree[i - 1] > 0: 
                arrThree[i] +=arrThree[i - 1]
                
        
        arrDiff = max(arrThree) - max(arrTwo)
        
        return (max(arrTwo) + (k-2)*arrDiff) % (10**9 + 7)
        
            
        
       
        


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:
        if k == 1:
            return self.maxSubArray(arr)
        else:
            arr_sum = sum(arr)
            
            if arr_sum > 0:
                max_sum = self.maxSubArray(arr ) + (k - 1) * arr_sum
                max_sum = max_sum%(10**9 + 7)
                print('pos')
            else:
                max_sum = self.maxSubArray(arr + arr) 
                print('neg')

        return max_sum
        
    def maxSubArray(self, arr):
        curr_sum = 0
        max_sum = 0
        for a in arr:
            curr_sum = max(curr_sum + a, a)
            max_sum = max(max_sum, curr_sum)
        
        return max_sum

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        current = arr[0]
        glob    = arr[0]
        
        for i in range(1, len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
                
        if k==1:
            return glob if glob > 0 else 0
        
        prevCurrent = current
        prevGlob    = glob
        
        for i in range(len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
        
        if prevGlob == glob or k==2:
            return glob if glob > 0 else 0
        
        afterCurrent = current
        afterGlob    = glob
        
        for i in range(len(arr)):
            
            if current + arr[i] >= arr[i]:
                current += arr[i]
            else:
                current = arr[i]
                
            if current > glob:
                glob = current
                
                
        glob += (glob - afterGlob) * (k-3)
        
        return glob % 1000000007 if glob > 0 else 0
            
            


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        m = 10**9+7
        
        def kadane(arr):
            cur =0
            res = 0
            for a in arr:
                cur = max(a, cur+a)
                res = max(res, cur)

            return res
        
        if k==1:
            return kadane(arr)
        else:
            if sum(arr)<=0:
                return kadane(arr*2)
            else:
                return (kadane(arr) + (k-1)*sum(arr))%m

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        c = sum(arr)
        out = 0
        straight_sum = arr[:]
        back_sum = arr[:]
        s = 0
        for i in range(1,len(straight_sum)):
            straight_sum[i] = max(straight_sum[i],straight_sum[i-1] + straight_sum[i])
            
        out = max(max(straight_sum),out)
        for i in range(len(arr)):
            out = max(out,arr[i])
            s +=arr[i]
            straight_sum[i] = s
        s = 0
        for i in range(len(arr)-1,-1,-1):
            s+=arr[i]
            back_sum[i] = s
        if k ==1:
            out = max(out,max(straight_sum),max(back_sum))
            return out
        if k > 2:
            out = max(out,max(straight_sum) + max(back_sum) + c*(k-2))
        out = max(max(straight_sum) + max(back_sum),out)
        
        return out % (10**9 + 7)


from math import inf as oo


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        total = sum(arr)
        kadanes = self.maxSubArraySum(arr)
        if (k < 2): return kadanes%(10**9+7)
        if (total > 0): return (kadanes + (k-1)*total)%(10**9+7)
        stitchedKadanes = self.maxSubArraySum(arr*2)
        return stitchedKadanes%(10**9+7)
    
    
    def maxSubArraySum(self, a):
        size = len(a)
        max_so_far = -oo
        max_ending_here = 0
        
        for i in a:
            max_ending_here += i
            if max_ending_here < 0: max_ending_here=0
            max_so_far = max(max_so_far, max_ending_here)

        return max_so_far

class Solution:
    def low_high(self,arr):
        low=0
       
        mhigh=0
        high=0
        peak=0
        s=0
        for i in range(len(arr)):
            s+=arr[i]
            if s>high:
                high=s
           
            if s>mhigh:
                mhigh=s
            if s<low:
                low=s
                high=s
            if high-low>peak:
                peak=high-low

        return low,high,peak,mhigh
    
    
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        low,high,peak,mhigh=self.low_high(arr)
        print((low,high,peak,mhigh))
        s=sum(arr)
        print(s)
        if k==1: 
            return peak%1000000007
        elif s>0:
            return (max(k-2,0)*s + mhigh + (s-low))%1000000007
        elif s<=0:
            return (max(peak,mhigh + (s-low),(s-low),0))%1000000007

        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        base = 10 ** 9 + 7
        if all([x >= 0 for x in arr]):
            return sum(arr) * k
        if all([x <= 0 for x in arr]):
            return 0
        
        sol1 = self.maxsub(arr)
        sol2 = self.maxsub(arr + arr)

        
        ma, mi = 0, 0
        presum = 0
        i = 0
        while i < len(arr):
            presum += arr[i]
            if presum > ma:
                ma = presum
            elif presum < mi:
                mi = presum
            i += 1
        if sum(arr) > 0:
            sol3 = max(ma + sum(arr) * (k-1), sum(arr) * k - mi)
            sol2 = sol2 + (k - 2) * sum(arr)
            return max(sol1, sol2, sol3) % base
        return max(sol1, sol2) % base
    
    
    
    def maxsub(self, arr):
        sol = 0
        temp = 0
        i = 0
        while i < len(arr):
            temp += arr[i]
            if temp < 0:
                temp = 0
            else:
                sol = max(sol, temp)
            i += 1 
        return sol 
                


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if sum(arr) > 0: 
            n = len(arr)
            s = (k*sum(arr))%1000000007
            l,r = [float('-inf') for _ in range(len(arr))],[float('-inf') for _ in range(len(arr))] 
            ml,mr = float('inf'),float('inf')
            for i in range(len(arr)):  
                l[i] = arr[i] + l[i-1] if i > 0 else arr[0]
                ml = min(ml,l[i])
                r[n-i-1] = arr[n-i-1] + r[n-i] if i > 0 else arr[-1]
                mr = min(mr, r[n-i-1])
            return s + (abs(ml) if ml < 0 else 0) + (abs(mr) if mr < 0 else 0)
        arr1 = arr + arr + arr
        arr = arr1
        print(arr)
        mx,n = float('-inf'),len(arr)
        left = [float('-inf') for _ in range(len(arr))] 
        for i in range(len(arr)):  
            left[i] = max(arr[i],arr[i] + left[i-1]) if i > 0 else arr[0]
            mx = max(mx, left[i])
        print(left)
        return max(mx, 0)
        
                    


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        
        mod = 10**9 + 7 
        def helper(arr, res = 0, cur = 0):
            for num in arr:
                cur = max(num, num + cur)
                res = max(res, cur)
            print(res)
            return res
        return ((k - 2) * max(sum(arr), 0) + helper(arr * 2)) % mod if k > 1 else helper(arr) % mod

from itertools import accumulate

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        if not arr: return 0
        MOD = 10 ** 9 + 7
        
        def kadane(arr):
            return max(accumulate(
                arr, func=lambda a, b: a + b if a > 0 else b, initial=0,
            ))
        return ((k - 2) * max(sum(arr), 0) + kadane(arr * 2)) % MOD if k >= 2 else kadane(arr)
    


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        # 1 -2 1  1 -2 1   1 -2 1   1 -2 1   1 -2 1
        if max(arr) <= 0:
            return 0
        if sum(arr) > 0:
            res = sum(arr) * (k - 2)
            dp = [0] * len(arr)
            dp[0] = arr[0]
            for i in range(1,len(arr)):
                dp[i] = dp[i - 1] + arr[i]
                    
            res += max(dp)
            dp = [0] * len(arr)
            dp[-1] = arr[-1]
            for i in range(len(arr) - 2, -1, -1):
                dp[i] = dp[i + 1] + arr[i]
                    
            res += max(dp)
            return (res)% (10 ** 9 + 7)
        
        cur , res = 0 , 0
        arr = arr + arr
        for num in arr:
            cur = max(cur+num,num)
            res = max(res,cur)
        
        return res % (10 ** 9 + 7)
        


from math import inf as oo


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        total = sum(arr)
        kadanes = self.maxSubArraySum(arr)
        if (k < 2): return kadanes%(10**9+7)
        if (total > 0): return (kadanes + (k-1)*total)%(10**9+7)
        stitchedKadanes = self.maxSubArraySum(arr*2)
        return stitchedKadanes%(10**9+7)
    
    
    def maxSubArraySum(self, a):
        size = len(a)
        max_so_far = -oo
        max_ending_here = 0
        
        for i in a:
            max_ending_here += i
            if max_ending_here < 0: max_ending_here=0
            max_so_far = max(max_so_far, max_ending_here)

        return max_so_far


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        def find_max(A):
            start = 0
            curr = 0
            res = 0
            for end in range(len(A)):
                curr += A[end]
                while curr<0:
                    curr -= A[start]
                    start += 1
                res = max(res, curr)
            return res
        
        
        if all(i<=0 for i in arr):
            return 0
        if k==1:
            return find_max(arr)
        # print (sum(arr)*k)
        res = max(find_max(arr), find_max(arr+arr), sum(arr)*k, find_max(arr+arr)+sum(arr)*(k-2))
        return res% (10**9 + 7)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        cum_sum = 0
        max_sum = 0
        MOD = 1000000007
        no_neg_num = True
        for var in arr:
            if var < 0:
                no_neg_num = False
                
        if no_neg_num:
            return sum(arr)*k
        
        
        for i in range(len(arr)):
            i = i%len(arr)
            cum_sum = max(cum_sum+arr[i],arr[i])
            if cum_sum > 0:
                cum_sum %= MOD
            max_sum = max(cum_sum,max_sum)
            
        if k == 1:
            return max_sum
            
        cum_sum2 = 0
        max_sum2 = 0
        for i in range(len(arr)*2):
            i = i%len(arr)
            cum_sum2 = max(cum_sum2+arr[i],arr[i])
            if cum_sum2 > 0:
                cum_sum2 %= MOD
            max_sum2 = max(cum_sum2,max_sum2)
            
        # print(max_sum)
        # print(cum_sum)
        # print(max_sum2)
        # print(cum_sum2)
        if sum(arr) > 0:
            return (max_sum+((sum(arr))%MOD)*(k-1))%MOD
        else:
            return max_sum2


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        # 1 -2 1  1 -2 1   1 -2 1   1 -2 1   1 -2 1
        if max(arr) <= 0:
            return 0
        if sum(arr) > 0:        # 需要找到最大的起始点
            res = sum(arr) * (k - 2)
            dp = [0] * len(arr)
            dp[0] = arr[0]
            for i in range(1,len(arr)):
                dp[i] = dp[i - 1] + arr[i]
                    
            res += max(dp)
            dp = [0] * len(arr)
            dp[-1] = arr[-1]
            for i in range(len(arr) - 2, -1, -1):
                dp[i] = dp[i + 1] + arr[i]
                    
            res += max(dp)
            return (res)% (10 ** 9 + 7)
        
        # 如果sum <= 0 那么只需要考虑两轮就好了
        cur , res = 0 , 0
        arr = arr + arr
        for num in arr:
            cur = max(cur+num,num)
            res = max(res,cur)
        
        return res % (10 ** 9 + 7)
        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        m = 10**9+7
        def kadane(arr):
            cur =0
            res = 0
            for a in arr:
                cur = max(a, cur+a)
                res = max(res, cur)

            return res
        if k==1:
            return kadane(arr)
        else:
            if sum(arr)<=0:
                return kadane(arr*2)
            else:
                return (kadane(arr) + (k-1)*sum(arr))%m


class Solution:
    def kadanes(self,arr,n):
        max_so_far = 0
        max_here = 0
        
        for i in range(n):
            max_here += arr[i % len(arr)]
            if max_so_far < max_here:
                max_so_far = max_here
            if max_here < 0:
                max_here = 0
        return max_so_far
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        
        if k >= 2:
            return self.kadanes(arr,len(arr)*2) + (k-2) * max(sum(arr),0) % (10**9+7)
        else:
            return self.kadanes(arr,len(arr)) % (10**9+7)

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        c = sum(arr)
        out = 0
        out = max (out,c*k)
        straight_sum = arr[:]
        back_sum = arr[:]
        s = 0
        kadan = arr[:]
        for i in range(1,len(kadan)):
            kadan[i] = max(kadan[i],kadan[i-1] + kadan[i])
        out = max(max(kadan),out)
        for i in range(len(arr)):
            out = max(out,arr[i])
            s +=arr[i]
            straight_sum[i] = s
        s = 0
        for i in range(len(arr)-1,-1,-1):
            s+=arr[i]
            back_sum[i] = s
        if k ==1:
            out = max(out,max(straight_sum),max(back_sum))
            return out
        if k > 2:
            out = max(out,max(straight_sum) + max(back_sum) + c*(k-2))
        out = max(max(straight_sum) + max(back_sum),out)
        
        return out % (10**9 + 7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        mod = 10 ** 9 + 7
        
        def kadane(arr):
            for i in range(1, len(arr)):
                arr[i] += arr[i - 1] if arr[i - 1] > 0 else 0
            return max(max(arr), 0)
        
        if k <= 2:
            return kadane(arr * k) % mod
        return (kadane(arr * 2) + (k - 2) * max(sum(arr), 0)) % mod        
        
        # s = sum(arr)
        # if s < 
        # mod = 10 ** 9 + 7
        # nums = arr * 2
        # n = len(arr)
        # for i in range(1, len(nums)):
        #     if nums[i - 1] > 0:
        #         nums[i] += nums[i - 1]
        # if k <= 2:
        #     max_sum = max(nums[: n * k])
        #     return max_sum % mod if max_sum >= 0 else 0
        # n1, n2 = max(nums[n: 2 * n]), max(nums[2 * n: 3 * n])
        # if n2 > n1:
        #     return n1 + (k - 2) * (n2 - n1) % mod
        # else:
        #     return n1 % mod if n1 >= 0 else 0
        
        
        def Kadane(arr, res = 0, cur = 0):
            for num in arr:
                cur = max(num, num + cur)
                res = max(res, cur)
            return res
        return ((k - 2) * max(sum(arr), 0) + Kadane(arr * 2)) % mod if k > 1 else Kadane(arr) % mod

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        mod = 10**9 + 7
        def Kadane(arr, res = 0, cur = 0):
            for num in arr:
                cur = max(num, num + cur)
                res = max(res, cur)
            return res
        sm = sum(arr)
        if sm >= 0:
            sm = sm * k
        print (sum(arr), Kadane(arr))
        if k == 1:
            return max(sm, Kadane(arr)) % mod
        return max(sm, max(sum(arr), 0) * (k - 2) + Kadane(arr * 2)) % mod

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        m = min(arr)
        M = max(arr)
        s = sum(arr)
        if m > 0 :
            return s*k
        if M < 0 :
            return 0
        
        ans = 0
        prefix_sum = 0 
        m_prefix_sum = 0
        
        for num in arr:
            prefix_sum += num
            ans = max(ans,prefix_sum-m_prefix_sum)
            m_prefix_sum = min(m_prefix_sum,prefix_sum)
        if k == 1:
            return ans
        
        prefix_sum = 0
        p_M = 0
        for num in arr:
            prefix_sum += num
            p_M = max(p_M,prefix_sum)
        suffix_sum = 0
        s_M = 0
        for num in arr[::-1]:
            suffix_sum+= num
            s_M = max(s_M,suffix_sum)
            
        return max(ans,p_M+s_M+(k-2)*s,p_M+s_M) % (10**9+7)
        


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        
        m = 10**9+7
        def kadane(arr):
            cur =0
            res = 0
            for a in arr:
                cur = max(a, cur+a)
                res = max(res, cur)

            return res
        if k==1:
            return kadane(arr)
        else:
            if sum(arr)<=0:
                return kadane(arr*2)
            else:
                return (kadane(arr) + (k-1)*sum(arr))%m

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        c = sum(arr)
        out = 0
        straight_sum = arr[:]
        back_sum = arr[:]
        s = 0
        kadan = arr[:]
        for i in range(1,len(kadan)):
            kadan[i] = max(kadan[i],kadan[i-1] + kadan[i])
        out = max(max(kadan),out)
        for i in range(len(arr)):
            out = max(out,arr[i])
            s +=arr[i]
            straight_sum[i] = s
        s = 0
        for i in range(len(arr)-1,-1,-1):
            s+=arr[i]
            back_sum[i] = s
        if k ==1:
            out = max(out,max(straight_sum),max(back_sum))
            return out
        if k > 2:
            out = max(out,max(straight_sum) + max(back_sum) + c*(k-2))
        out = max(max(straight_sum) + max(back_sum),out)
        
        return out % (10**9 + 7)


class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        L=arr
        m=0
        t=0
        l=0
        lm=0
        sm=0
        for i in L:
            l+=i
            lm=max(lm,l)
            if(t+i>0): t+=i
            else: t=0
            m=max(m,t)
            sm+=i
        
        r=0
        rm=0
        for i in range(len(L)-1,-1,-1):
            r+=L[i]
            rm=max(rm,r)
            
            
        #print(lm,rm,m)
            
        if(k==1): return m%(10**9+7)
        elif(k==2): return max(m,(rm+lm))%(10**9+7)
        else:
            s=(rm+lm)%(10**9+7)
            if(sm>0):
                return max(m,(s+sm*(k-2)))%(10**9+7)
            else: return max(s,m)%(10**9+7)