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 ```python 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** ```text 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** ```text 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** ```text 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.