Count Collections of Nonoverlapping Segments

### Problem Points lie at integer coordinates `0..n-1` on a line. Draw exactly `k` segments with endpoints among these points. Every segment has distinct endpoints, segment interiors cannot overlap, and consecutive segments may share an endpoint. Some points may remain unused. Return the number of different segment sets modulo `10^9 + 7`. ```cpp class Solution { public: int numberOfSets(int n, int k); }; ``` ### Examples **Example 1:** ```text n = 4, k = 1 Output: 6 Explanation: Choose any two distinct points from four as endpoints. ``` **Example 2:** ```text n = 5, k = 3 Output: 7 Explanation: Four placements use three unit segments among the four gaps; three more use lengths that total four with one segment of length two. ``` ### Constraints - `2 <= n <= 1000`. - `1 <= k <= n-1`. ### Clarifying Questions The segments are an unordered set, naturally sorted by position. Sharing an endpoint is legal, while sharing positive length is not. ```hint Inspect the structure Which configurations share only endpoints, and which overlap over a positive length? ``` ### Reasoning checkpoints - Preserve the distinction between endpoint touching and interior overlap. - Count each segment set once and apply the modulus. ### Optional extensions What binomial expression would result if shared endpoints were forbidden?