<p>Given <code>n</code> points on a 1-D plane, where the <code>i<sup>th</sup></code> point (from <code>0</code> to <code>n-1</code>) is at <code>x = i</code>, find the number of ways we can draw <strong>exactly</strong> <code>k</code> <strong>non-overlapping</strong> line segments such that each segment covers two or more points. The endpoints of each segment must have <strong>integral coordinates</strong>. The <code>k</code> line segments <strong>do not</strong> have to cover all <code>n</code> points, and they are <strong>allowed</strong> to share endpoints.</p>

<p>Return <em>the number of ways we can draw </em><code>k</code><em> non-overlapping line segments</em><em>.</em> Since this number can be huge, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/07/ex1.png" style="width: 179px; height: 222px;" />
<pre>
<strong>Input:</strong> n = 4, k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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)}.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, k = 1
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 30, k = 7
<strong>Output:</strong> 796297179
<strong>Explanation:</strong> The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10<sup>9</sup> + 7 gives us 796297179.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= n-1</code></li>
</ul>

// Idea: DP, and suffix sum.
// let F_k[i] be the count of k-sets in A[i...n-1],
// then we have
// F_1[i] = n-1-i // count of 1-set starting at [i] and endint at [j], j > i,
//         + suffix_sum(F_1[i+1 ...]). // suffix sum
// F_k[i] = sum_of(F[k-1][j] for j = i+1 to n-1) // starting at [i], ending at
// [j]
//         + suffix_sum(F[k][i+1 ... ])
//
class Solution1_dp {
    const int ModBase = 1'000'000'007;
public:
    int numberOfSets_DP(int n, int k) {
        // DP array
        // f is the current row, g is the previous row
        vector<long long> f(n), g(n);
        // init for k = 1
        for (int i = n - 1, sum = 0; i >= 0; --i) {
            f[i] = n - 1 - i;
            f[i] += sum;
            f[i] %= ModBase;
            sum = f[i];
        }
        // for k' = 2 ... k
        for (int m = 2; m <= k; ++m) {
            swap(f, g);
            for (int i = n - 1, gsum = 0, fsum = 0; i >= 0; --i) {
                gsum = (gsum + g[i]) % ModBase;
                f[i] = (gsum + fsum) % ModBase;
                fsum = (fsum + f[i]) % ModBase;
            }
        }
        return f[0];
    }
};

// Idea: combinatorics: stars and bars:
// https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments/solutions/898727/c-o-n-solution-explained-in-detail-using-stars-and-bars/
const int mod=1e9+7,MX=2e3+10;
int mult(int a,int b){return (1ll*a*b)%mod;}
int fact[MX],inv[MX],invfact[MX];
void init_INV(){
	fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1;
    for (int i = 2; i < MX; i++) {
        fact[i] = mult(fact[i - 1], i);
        inv[i] = mult(inv[mod % i], mod - mod / i);
        invfact[i] = mult(invfact[i - 1], inv[i]);
    }
}
int ncr(int n,int r){
	if(r > n) return 0;
	return (1LL * fact[n] * invfact[n-r] % mod) * 1LL *invfact[r] % mod;
}

class Solution {
public:
    int numberOfSets(int n, int k) {
        init_INV();
        return ncr(n + k - 1, 2 * k);
    }
};
7300