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

class Solution {
public:


// BOILERPLATE TEMPLATE (ignore this for now, understand the core logic first)

#define ll long long

    vector<ll> factorial;

    static const ll MOD = 1e9 + 7;

ll modpow(ll base, ll exp, ll M=MOD) {
  base %= M;
  ll result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % M;
    base = ((ll)base * base) % M;
    exp >>= 1;
  }
  return result;
}

ll modinv(ll a, ll m){ return modpow(a,m-2,m); }
ll modadd(ll a, ll b, ll m = MOD) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll modsub(ll a, ll b, ll m = MOD) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll modmul(ll a, ll b, ll m = MOD) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll moddiv(ll a, ll b, ll m = MOD) { a = a % m; b = b % m; return (modmul(a, modinv(b, m), m) + m) % m; } //only when m is prime

    void precomputeFactorials () {
        factorial.resize(1005, 1);
        for (ll i=1; i<=1004; i++) {
            factorial[i] = (factorial[i-1] * (ll) i) % MOD;
        }
    }

// combination formula
ll nCr (int n, int r) {
    return moddiv(factorial[n], modmul(factorial[r], factorial[n-r]));
};







// CORE IMPLEMENTATION
    int numberOfSets(ll n, ll k) {
        precomputeFactorials(); // Precompute factorials

        ll ans = 0;
        n--; // IMP: Decrease n by 1 because we're considering n as possible lines and not the points

        // Iterate over all possible sums
        for (ll sum = k; sum <= n; sum++) {
            // Calculate x = C(sum - 1, k - 1)
            ll x = nCr (sum-1, k-1);

            int gap = n - sum;

            // Calculate y = C(k + gap, k)
            ll y = nCr (k+gap, k);

            // Update the answer using the calculated values of x and y
            ans = modadd(ans, modmul(x, y));
        }

        return ans;
    }
};
8200