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