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: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

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

		def kadane(numbers):
			best = 0
			curr = 0
			for x in numbers:
				curr = max(0, curr + x)
				best = max(best, curr)
			return best
		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)
		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
		elif 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
		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 = 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(1000000000.0 + 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)
			min_lsum = min(lsum, min_lsum)
			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


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)
		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, 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
		arrTwo = arr * 2
		for i in range(1, len(arrTwo)):
			if arrTwo[i - 1] > 0:
				arrTwo[i] += arrTwo[i - 1]
		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)
		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:
		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)
		elif 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)


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:
		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)


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)
		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)
		if sum(arr) > 0:
			return (max_sum + sum(arr) % MOD * (k - 1)) % MOD
		else:
			return max_sum2


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:
		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:
		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)
		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)