Given n points on a 1-D plane, where the ith 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 109 + 7.

&nbsp;
Example 1:

Input: n = 4, k = 2
Output: 5
Explanation: The two line segments are shown in red and blue.
The image above shows the 5 different ways {(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: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.


Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 1000
	1 &lt;= k &lt;= n-1


class Solution:
    def numberOfSets(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        @lru_cache(None)
        def dp(i, k, isStart):
            if k == 0: return 1 # Found a way to draw k valid segments
            if i == n: return 0 # Reach end of points
            ans = dp(i+1, k, isStart) # Skip ith point
            if isStart:
                ans += dp(i+1, k, False) # Take ith point as start
            else:
                ans += dp(i, k-1, True) # Take ith point as end
            return ans % MOD
        return dp(0, k, True)
class Solution {
    Integer[][][] memo;
    int n;
    public int numberOfSets(int n, int k) {
        this.n = n;
        this.memo = new Integer[n+1][k+1][2];
        return dp(0, k, 1);
    }
    int dp(int i, int k, int isStart) {
        if (memo[i][k][isStart] != null) return memo[i][k][isStart];
        if (k == 0) return 1; // Found a way to draw k valid segments
        if (i == n) return 0; // Reach end of points

        int ans = dp(i+1, k, isStart); // Skip ith point
        if (isStart == 1)
            ans += dp(i+1, k, 0); // Take ith point as start
        else
            ans += dp(i, k-1, 1); // Take ith point as end

        return memo[i][k][isStart] = ans % 1_000_000_007;
    }
}
class Solution {
public:
    int MOD = 1e9+7;
    int sumDyp(int n, int k, vector<vector<int>> &dp, vector<vector<int>> &sumDp)
    {
        if(n < 2)
            return 0;
        
        if(sumDp[n][k] != -1)
            return sumDp[n][k];
        
        sumDp[n][k] = ((sumDyp(n-1, k, dp, sumDp)%MOD) + (dyp(n, k, dp, sumDp)%MOD))%MOD;
        return sumDp[n][k];
    }
        
    int dyp(int n, int k, vector<vector<int>> &dp, vector<vector<int>> &sumDp)
    {
        if(n < 2)
            return 0;
        
        if(dp[n][k] != -1)
            return dp[n][k];
        
        if(k == 1)
        {
            dp[n][k] = ((((n-1)%MOD) * (n%MOD))%MOD)/2;
            return dp[n][k];
        }
        
        
        int ans1 = dyp(n-1, k, dp, sumDp);
        int ans2 = sumDyp(n-1, k-1, dp, sumDp);
        
        int ans = ((ans1%MOD) + (ans2%MOD))%MOD;
        dp[n][k] = ans;
        return ans;
    }
    
    int numberOfSets(int n, int k) 
    {
        vector<vector<int>> dp(n+1, vector<int>(k+1, -1));
        vector<vector<int>> sumDp(n+1, vector<int>(k+1, -1));
        return dyp(n, k, dp, sumDp);
    }
};
var numberOfSets = function(n, k) {
    return combinations(n+k-1,2*k)%(1e9+7)
};
var combinations=(n,k)=>{
    var dp=[...Array(n+1)].map(d=>[...Array(k+1)].map(d=>1))
    for (let i = 1; i <=n; i++) 
        for (let k = 1; k <i; k++)
            dp[i][k]=(dp[i-1][k-1]+dp[i-1][k]) %(1e9+7)     
    return dp[n][k]
}
Number of Sets of K Non-Overlapping Line Segments