<p>Given an integer array <code>arr</code> and an integer <code>k</code>, modify the array by repeating it <code>k</code> times.</p>

<p>For example, if <code>arr = [1, 2]</code> and <code>k = 3 </code>then the modified array will be <code>[1, 2, 1, 2, 1, 2]</code>.</p>

<p>Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be <code>0</code> and its sum in that case is <code>0</code>.</p>

<p>As the answer can be very large, return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2], k = 3
<strong>Output:</strong> 9
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,-2,1], k = 5
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [-1,-2], k = 7
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= arr[i] &lt;= 10<sup>4</sup></code></li>
</ul>

r'''
# Requirements

n = len(arr)
1 <= n <= 100,000
1 <= k <= 100,000
-10,000 <= arr[i] <= 10,000

# Edge cases

1. Max subarray sum is negative
    - Selecting an empty subarray is allowed
2. Array has no negative elements
3. Array sum is positive
4. Max sum spans across two repetitions as if the array is circular
5. Max sum is too large
    - Mod 10^9 + 7

# Solutions

1. Brute force
    - O((kn) ^2) time, O(1) auxiliary space
2. Kadane's algorithm, at most two passes
    - O(n) time, O(1) auxiliary space
'''
MOD = 10 ** 9 + 7

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

        # Run Kadane's algorithm once
        max_sum, curr_sum = arr[0], 0

        def kadane() -> None:
            nonlocal max_sum, curr_sum

            for num in arr:
                curr_sum = max(num + curr_sum, num)
                max_sum = max(max_sum, curr_sum)

        kadane()

        # Max sum is zero or negative - select an empty subarray
        # k == 1 - return immediately
        if k == 1 or max_sum <= 0:
            return max(max_sum, 0)

        # Run Kadane's algorithm a second time to find the max sum as if the array is circular
        kadane()

        # If the sum of elements is positive, max sum can grow indefinitely
        arr_sum = sum(arr)
        if arr_sum > 0:
            return (max_sum + arr_sum * (k - 2)) % MOD

        return max_sum % MOD
31100