MOD = 10**9 + 7 max_fact = 200000 # Precompute up to 2e5 to handle all possible cases # Precompute factorial and inverse factorial arrays fact = [1] * (max_fact + 1) for i in range(1, max_fact + 1): fact[i] = fact[i-1] * i % MOD inv_fact = [1] * (max_fact + 1) inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD) for i in range(max_fact -1, -1, -1): inv_fact[i] = inv_fact[i+1] * (i+1) % MOD def comb(n, k): if n < 0 or k < 0 or n < k: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD # Read input N, d, K = map(int, input().split()) # Check if K is within the valid range if K < N or K > d * N: print(0) else: S = K - N m = min(N, S // d) result = 0 for k in range(m + 1): c_n_k = comb(N, k) a = S - k * d + (N - 1) c_a = comb(a, N - 1) term = pow(-1, k, MOD) * c_n_k % MOD term = term * c_a % MOD result = (result + term) % MOD result = (result + MOD) % MOD # Ensure non-negative print(result)