Max total of k consecutive bags over disjoint valued segments, modulo 1e9+7

Bags stand in a single row that never ends, one bag at every positive integer position 1, 2, 3, .... You are given segments, where segments[i] = [l, r, v] means that every bag at a position from l to r inclusive holds v units of money. No two segments share a position, and every bag that no segment covers is empty and holds 0.

Choose k consecutive bags, meaning the bags at positions s, s + 1, ..., s + k - 1 for some start s >= 1. Let M be the largest total amount of money any such choice collects. Return M modulo 1,000,000,007.

Function Signature

def max_k_consecutive_bags(k: int, segments: list[list[int]]) -> int:

Rules

• The chosen positions must be consecutive. They may include empty bags, and they may cover a segment only partly: every covered bag of a segment contributes its full v, and the uncovered bags of that segment contribute nothing.
• segments may be given in any order. Two segments may be adjacent (one ends at p and another starts at p + 1), but they never overlap.
• Compare the exact, unreduced totals to find M, and apply the modulo only to M. A larger exact total can leave a smaller remainder, as Example 3 shows.
• The return value is a single integer, so it does not matter which start s achieves M.

Constraints

• 1 <= n <= 200,000, where n = len(segments)
• 1 <= l <= r <= 10^9 for every segment
• 1 <= v <= 10^6 for every segment
• 1 <= k <= 10^9, and k may exceed the distance spanned by all the segments together
• Positions and k fit in a 32-bit signed integer, but an exact total can reach 10^9 * 10^6 = 10^15, which is beyond 2^31 - 1. Every exact total stays below 2^53, and the returned value is below 1,000,000,007.

Examples

Example 1

Input: k = 5, segments = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
Output: 16

Positions 3 through 7 hold 2, 2, 0, 5, 7, which sums to 16. No other five consecutive bags collect more, and 16 is already below the modulus.

Example 2

Input: k = 5, segments = [[10, 12, 4], [3, 5, 1], [7, 8, 6]]
Output: 20

The segments arrive unsorted. Positions 7 through 11 hold 6, 6, 0, 4, 4, a total of 20: both bags of [7, 8, 6], the empty bag at position 9, and only the first two bags of [10, 12, 4].

Example 3

Input: k = 1012, segments = [[1, 1000, 1000000], [1001, 1012, 1], [5001, 6012, 988000]]
Output: 5

Positions 1 through 1012 collect 1000 * 1,000,000 + 12 * 1 = 1,000,000,012, the largest exact total, so M = 1,000,000,012 and the answer is M modulo 1,000,000,007, which is 5. Positions 5001 through 6012 collect only 1012 * 988,000 = 999,856,000. Its remainder is larger, but its exact total is smaller, so it does not decide the answer.