<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>

// 2024-09-13, 星期五, 八月十一, 甲辰年, 龙年, 癸酉月, 庚辰日
// https://github.com/shionryuu/leetcode-rust
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

class Comb {
private:
  const long long MOD;
  int n;
  vector<long long> fact;
  vector<long long> inv_fact;

public:
  Comb(int n, long long MOD = 1e9 + 7) : MOD(MOD), n(n), fact(n + 1, 0), inv_fact(n + 1, 0) {
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
      fact[i] = fact[i - 1] * i % MOD;
    }
    inv_fact[n] = binpow(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; --i) {
      inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    };
  }

  int nCr(int n, int r) const {
    if (r < 0 || r > n) {
      return 0;
    }
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
  }
};

class Solution {
public:
  // 2024-09-13, 星期五, 八月十一, 甲辰年, 龙年, 癸酉月, 庚辰日
  // https://github.com/shionryuu/leetcode-rust
  int numberOfSets(int n, int k) {
    const long long MOD = 1e9 + 7;

    if (n + k - 1 < 2 * k) {
      return 0;
    }

    const Comb c(2000, MOD);
    return c.nCr(n + k - 1, 2 * k);
  }
};
10000