Loading problem…
Given `n` points on a 1-D plane, where the `i`th point (from `0` to `n-1`) is at `x = i`, find the number of ways we can draw **exactly** `k` **non-overlapping** line segments such that each segment covers two or more points. The endpoints of each segment must have **integral coordinates**. The `k` line segments **do not** have to cover all `n` points, and they are **allowed** to share endpoints. Return the number of ways we can draw `k` non-overlapping line segments. Since this number can be huge, return it **modulo** `10^9 + 7`.
Example 1
Input: n = 4, k = 2
Output: 5
Explanation: The 5 ways to draw 2 non-overlapping segments over points 0..3: {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.
Example 2
Input: n = 3, k = 1
Output: 3
Explanation: One segment over points 0,1,2: {(0,1)}, {(0,2)}, {(1,2)}.
Example 3
Input: n = 30, k = 7
Output: 796297179
Explanation: 3796297200 ways total, taken modulo 10^9 + 7.
Scan points right-to-left; dp[i][j] counts ways to place j segments using points i..n-1, and a suffix sum collapses the 'where does the next segment start' choice into O(1).
Run checks all cases above. Submit evaluates all test cases.