Editorial for Lecture Gap

Approach

The gap condition $x_{i+1} \ge x_i + g$ makes the sequence strictly spaced. Shift it back to an ordinary non-decreasing sequence by setting

$y_i = x_i - (i - 1)g$.

Then $x_{i+1} \ge x_i + g$ becomes $y_{i+1} \ge y_i$, and the bounds become

$1 \le y_1 \le y_2 \le \cdots \le y_k \le n - (k - 1)g$.

Let $m = n - (k - 1)g$. If $m < 1$, no such $y$ exists and the answer is $0$ (do not evaluate a binomial coefficient with a negative upper index).

Otherwise the number of non-decreasing sequences of length $k$ with values in $\{1, \ldots, m\}$ is combinations with repetition:

$\binom{m + k - 1}{k}$.

Special cases worth checking by hand:

• $g = 0$: no forced gap, so the answer is $\binom{n + k - 1}{k}$ (vanilla non-decreasing sequences in $[1, n]$);
• $g = 1$: the sequence is strictly increasing, so $m = n - k + 1$ and the answer is $\binom{n}{k}$;
• $k = 1$: $m = n$ and the answer is $n$.

Precompute factorials and inverse factorials modulo $10^9 + 7$ up to $n + k$. Time is $O(n + k)$.

Solution (Python)

MOD = 10**9 + 7
MAXN = 2 * 10**6 + 5

fact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD
invfact = [1] * MAXN
invfact[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD


def nCr(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD


n, k, g = map(int, input().split())
m = n - (k - 1) * g
if m < 1:
    print(0)
else:
    print(nCr(m + k - 1, k))