Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree.

A k-tree is an infinite rooted tree where:

  each vertex has exactly k children;  each edge has some weight;  if we look at the edges that goes from some vertex to its children (exactly k edges), then their weights will equal 1, 2, 3, ..., k. 

The picture below shows a part of a 3-tree.

 

 [Image]

    As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight n (the sum of all weights of the edges in the path) are there, starting from the root of a k-tree and also containing at least one edge of weight at least d?".

Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (10^9 + 7). 


-----Input-----

A single line contains three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).


-----Output-----

Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7). 


-----Examples-----
Input
3 3 2

Output
3

Input
3 3 3

Output
1

Input
4 3 2

Output
6

Input
4 5 2

Output
7

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Implementation


Solutions:
import sys
(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
if d > n:
	print(0)
	sys.exit(0)
c = [0] * (n + 1)
cod = [0] * (n + 1)
for i in range(1, n + 1):
	c[i] = 1 if i <= k else 0
	cod[i] = 1 if i < d else 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		else:
			c[i] = (c[i] + c[i - j]) % mod
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		elif j < d:
			cod[i] = (cod[i] + cod[i - j]) % mod
print((c[n] - cod[n]) % mod)


M = 10 ** 9 + 7

class paths:

	def __init__(self):
		super().__init__()
		self.dp = {}

	def no_of_paths(self, n, k):
		if n in self.dp:
			return self.dp[n]
		if n == 0:
			return 1
		elif n < 0:
			return 0
		else:
			paths = 0
			for i in range(1, k + 1):
				val = self.no_of_paths(n - i, k)
				paths += val
			self.dp[n] = paths
			return paths
(n, k, d) = map(int, input().split())
pathk = paths()
pathd = paths()
print((pathk.no_of_paths(n, k) - pathd.no_of_paths(n, d - 1)) % M)


import time, math, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x))

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count

def solve():
	mod = 1000000000.0 + 7
	(n, k, d) = IP()
	dp = [0] * (n + 1)
	dp2 = [0] * (n + 1)
	(dp[0], dp2[0]) = (1, 1)
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j < 0:
				break
			else:
				dp[i] = (dp[i] + dp[i - j]) % mod
	for i in range(1, n + 1):
		for j in range(1, d):
			if i - j < 0:
				break
			else:
				dp2[i] = (dp2[i] + dp2[i - j]) % mod
	print(int((dp[n] - dp2[n]) % mod))
solve()


import os
import sys
if os.path.exists('C:\\Users\\User\\codeforces'):
	f = iter(open('A.txt').readlines())

	def input():
		return next(f).strip()
else:
	input = lambda : sys.stdin.readline().strip()
fprint = lambda *args: print(*args, flush=True)
(n, k, d) = map(int, input().split())
M = 10 ** 9 + 7
N = 101
lessD = [0] * N
lessD[0] = 1
for i in range(N):
	for add in range(1, d):
		if i + add < N:
			lessD[i + add] += lessD[i]
anyD = [0] * N
anyD[0] = 1
for i in range(N):
	for add in range(1, k + 1):
		if i + add < N:
			anyD[i + add] += anyD[i]
res = 0
for i in range(d, k + 1):
	for j in range(0, n - i + 1):
		k = n - i - j
		res = (res + lessD[j] * anyD[k]) % M
print(res)


from sys import stdin, stdout
input = stdin.readline
mp = lambda : map(int, input().split())
it = lambda : int(input())
(n, k, d) = mp()
mod = 10 ** 9 + 7
dp = [0] * (n + 1)
dp1 = [0] * (n + 1)
dp[0] = 1
dp1[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i >= j:
			dp[i] += dp[i - j]
		dp[i] %= mod
	for r in range(1, d):
		if i >= r:
			dp1[i] += dp1[i - r]
		dp1[i] %= mod
print((dp[n] - dp1[n]) % mod)


(n, k, d) = map(int, input().split())
l = max(n, k)
m = min(n, k)
dp = [0] * (2 * l + 1)
dp[l] = 1
dp2 = dp.copy()
for i in range(l + 1, l + n + 1):
	for j in range(1, m + 1):
		dp[i] += dp[i - j]
	for j in range(1, d):
		dp2[i] += dp2[i - j]
print((dp[l + n] - dp2[l + n]) % (10 ** 9 + 7))


(n, k, d) = map(int, input().split())
ans = {}

def dp_solve(n, k):
	if k == 0:
		return 0
	ans[0] = 1
	ans[1] = 1
	for i in range(2, n + 1):
		cur_t = 0
		for j in range(1, k + 1):
			if i - j >= 0:
				cur_t += ans[i - j]
		ans[i] = cur_t
	return ans[n]
a = dp_solve(n, k)
b = dp_solve(n, d - 1)
print((a - b) % int(1000000000.0 + 7))


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, k, d) = I()
md = 10 ** 9 + 7
dp = [[0, 0] for i in range(102)]
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		if j < d:
			dp[i][0] = (dp[i][0] + dp[i - j][0]) % md
			dp[i][1] = (dp[i][1] + dp[i - j][1]) % md
		else:
			dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % md
print(dp[n][1])


dpall = []
dpd = []
MOD = 1000000007
(n, k, d) = map(int, input('').split(' '))
for i in range(105):
	dpall.append(None)
	dpd.append(None)

def solveD(u):
	if u == 0:
		return 1
	if dpd[u] != None:
		return dpd[u]
	ans = 0
	for i in range(1, min(min(d - 1, k), u) + 1):
		ans += solveD(u - i)
	dpd[u] = ans
	return ans

def solveAll(u):
	if u == 0:
		return 1
	if dpall[u] != None:
		return dpall[u]
	ans = 0
	for i in range(1, min(k, u) + 1):
		ans = ans + solveAll(u - i)
	dpall[u] = ans
	return ans
res = solveAll(n) - solveD(n)
print(res % MOD)


(n, k, d) = map(int, input().split())
l = [1] + [0] * n
m = [1] + [0] * n
for i in range(0, n + 1):
	for j in range(1, d):
		if i + j <= n:
			l[i + j] += l[i]
for i in range(0, n + 1):
	for j in range(1, k + 1):
		if i + j <= n:
			m[i + j] += m[i]
print((m[n] - l[n]) % (10 ** 9 + 7))


MOD = int(1000000000.0 + 7)
(n, k, d) = map(int, input().split())
memo = [[[-1] * 2 for i in range(n + 1)] for j in range(n + 1)]

def add(x, y):
	return ((x % MOD + MOD) % MOD + (y % MOD + MOD) % MOD) % MOD

def dp(dep, s, cnt):
	if s > n:
		return 0
	if s == n:
		return int(cnt)
	if memo[dep][s][cnt] != -1:
		return memo[dep][s][cnt]
	memo[dep][s][cnt] = 0
	for i in range(1, k + 1):
		memo[dep][s][cnt] = add(memo[dep][s][cnt], dp(dep + 1, s + i, cnt or i >= d))
	return memo[dep][s][cnt]
print(dp(0, 0, False))


def fn(n, k, p, dp):
	m = 1000000007
	if n == 0:
		return 1
	t = [0] * (k + 1)
	for i in range(1, k + 1):
		if i == p:
			break
		if n < i:
			break
		t[i] = 1
		if dp[n - i] != -1:
			u = dp[n - i]
		else:
			u = fn(n - i, k, p, dp)
			dp[n - i] = u % m
		t[i] = t[i] * (u % m) % m
	v = 0
	for i in range(len(t)):
		v = (v + t[i]) % m
	return v
m = 1000000007
(n, k, p) = map(int, input().split())
dp1 = [-1] * (n + 1)
dp2 = [-1] * (n + 1)
print((fn(n, k, -1, dp1) - fn(n, k, p, dp2) + m) % m)


import sys
import time

def read_line(cast=None):
	if cast is not None:
		return cast(input().strip())
	else:
		return input().strip()

def read_list(cast=int):
	return list(map(cast, read_line().split()))
INTMAX = 1000000007
res = 0

def dfs(n, k, d, t=False):
	global res, INTMAX
	if n < 0:
		return
	if n == 0 and (not t):
		return
	if n == 0 and t:
		res = (res + 1) % INTMAX
		return
	for i in range(1, k + 1):
		dfs(n - i, k, d, t or i >= d)

def solve(n, k, d):
	global res, INTMAX
	res = 0
	dp = [[0 for _ in range(2)] for _ in range(101)]
	dp[0][0] = 1
	dp[0][1] = 0
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j < 0:
				break
			if j < d:
				dp[i][0] = (dp[i][0] + dp[i - j][0]) % INTMAX
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % INTMAX
			else:
				dp[i][1] = (dp[i][1] + dp[i - j][0]) % INTMAX
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % INTMAX
	print(dp[n][1])
(n, k, d) = read_list()
solve(n, k, d)


import collections
import itertools
from functools import lru_cache
import sys
import math
MOD = int(1000000000.0) + 7

def helper():
	pass

def solve():
	(n, k, d) = map(int, input().split(' '))

	@lru_cache(None)
	def dfs(score, pred):
		if score == 0:
			return 1 if pred else 0
		elif score < 0:
			return 0
		else:
			ans = 0
			for i in range(1, k + 1):
				if score - i >= 0:
					if i >= d:
						ans = (ans % MOD + dfs(score - i, True) % MOD) % MOD
					else:
						ans = (ans % MOD + dfs(score - i, pred) % MOD) % MOD
				else:
					break
			return ans
	print(dfs(n, False))
t = 1
for _ in range(t):
	solve()


s = input()
s1 = s.split()
tot = int(s1[0])
n = int(s1[1])
d = int(s1[2])
l = [int(i) for i in range(1, n + 1)]
final = 0
temp = tot
dp = [0 for i in range(temp + 1)]
dp[0] = 1
for i in range(1, temp + 1):
	sum1 = 0
	for j in range(1, n + 1):
		if i - j >= 0:
			sum1 = sum1 + dp[i - j]
	dp[i] = sum1
temp2 = dp[tot]
dp = [0 for i in range(temp + 1)]
dp[0] = 1
for i in range(1, temp + 1):
	sum1 = 0
	for j in range(1, d):
		if i - j >= 0:
			sum1 = sum1 + dp[i - j]
	dp[i] = sum1
temp3 = dp[tot]
print((temp2 - temp3) % 1000000007)


(n, k, d) = map(int, input().split())
import sys
sys.setrecursionlimit(10 ** 5)
mod = int(1000000000.0 + 7)
import functools

@functools.lru_cache(None)
def rec(n, d):
	if n < 0:
		return 0
	if n == 0:
		return d == 0
	res = 0
	for i in range(1, k + 1):
		if i >= d:
			res += rec(n - i, 0)
		else:
			res += rec(n - i, d)
		res %= mod
	return res % mod
print(rec(n, d) % mod)


(n, v, d) = list(map(int, input().split()))
dp = [[0] * 2 for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	for k in range(1, min(i, v) + 1):
		dp[i][0] += dp[i - k][0]
		if k >= d:
			dp[i][1] += dp[i - k][0]
		else:
			dp[i][1] += dp[i - k][1]
print(dp[n][1] % (10 ** 9 + 7))


bignum = 10 ** 9 + 7
(n, k, d) = [int(i) for i in input().split()]
D = [[0 for j in range(2)] for i in range(n + 1)]
D[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		if j < d:
			D[i][0] += D[i - j][0]
			D[i][1] += D[i - j][1]
			D[i][0] %= bignum
			D[i][1] %= bignum
		else:
			D[i][1] += D[i - j][0] + D[i - j][1]
			D[i][1] %= bignum
print(D[n][1])


(n, k, d) = map(int, input().split())
ai = [0] * (n + 1)
k = min(n, k)
ai[0] = 1
mode = 10 ** 9 + 7
for i in range(1, k):
	for j in range(i):
		ai[i] += ai[j]
for i in range(k, n + 1):
	for j in range(1, k + 1):
		ai[i] += ai[i - j]
d = min(n, d - 1)
ai2 = [0] * (n + 1)
ai2[0] = 1
for i in range(1, d):
	for j in range(i):
		ai2[i] += ai2[j]
for i in range(d, n + 1):
	for j in range(1, d + 1):
		ai2[i] += ai2[i - j]
print((ai[n] - ai2[n]) % mode)


(n, k, d) = map(int, input().split())
N = 10 ** 9 + 7
L = max(n, k) + 1
wd = [0] * L
pwd = [0] * L
nd = [1] * L
pnd = [1] * L
for i in range(1, d):
	nd[i] = pnd[i - 1] % N
	pnd[i] = (pnd[i - 1] + nd[i]) % N
for i in range(d, k + 1):
	nd[i] = (pnd[i - 1] - pnd[i - d]) % N
	pnd[i] = (pnd[i - 1] + nd[i]) % N
	wd[i] = (pnd[i - d] + pwd[i - 1]) % N
	pwd[i] = (pwd[i - 1] + wd[i]) % N
for i in range(k + 1, n + 1):
	nd[i] = (pnd[i - 1] - pnd[i - d]) % N
	pnd[i] = (pnd[i - 1] + nd[i]) % N
	wd[i] = (pnd[i - d] - pnd[i - k - 1] + pwd[i - 1] - pwd[i - k - 1]) % N
	pwd[i] = (pwd[i - 1] + wd[i]) % N
print(wd[n])


(n, k, d) = [int(i) for i in input().split()]
mod = 1000000000.0 + 7
dp = [[-1 for i in range(2)] for j in range(n + 1)]

def dfs(cur_sum: int, chk: bool):
	if cur_sum == n and chk == True:
		return 1
	if cur_sum == n and chk == False:
		return 0
	if cur_sum > n:
		return 0
	if dp[cur_sum][chk] != -1:
		return dp[cur_sum][chk]
	ans = 0
	for i in range(1, k + 1):
		if i < d:
			ans += dfs(cur_sum + i, chk)
		else:
			ans += dfs(cur_sum + i, True)
	dp[cur_sum][chk] = ans % mod
	return ans % mod
ans = int(dfs(0, False))
print(ans)


import math
MOD = 10 ** 9 + 7
(n, k, d) = [int(i) for i in input().split()]
dp = [0] * (n + 1)
dp1 = [0] * (n + 1)
for i in range(n + 1):
	if i <= k:
		dp[i] = 1
		if i < d:
			dp1[i] = 1
dp[0] = 0
dp1[0] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j > i:
			continue
		dp[i] = (dp[i] + dp[i - j]) % MOD
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j > i:
			continue
		if j < d:
			dp1[i] = (dp1[i] + dp1[i - j]) % MOD
print((dp[n] - dp1[n]) % MOD)


Mod = 1000000007
(n, k, d) = map(int, input().split())
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j <= i:
			if j < d:
				dp[i][0] = (dp[i - j][0] + dp[i][0]) % Mod
				dp[i][1] = (dp[i - j][1] + dp[i][1]) % Mod
			else:
				dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % Mod
print(dp[n][1])


import sys
import collections
import math
import functools
import itertools
import bisect
import operator
import heapq
import random
true = True
false = False
null = None
SLOW = True
memoi = functools.lru_cache(None)
tcid = 0
tcmax = 99999999

def fast():
	SLOW = False

def compute(val, func):
	return func(val)

def seq(lo, hi, step=1):
	return range(lo, hi + 1, step)

def sround(val, nd):
	return f'{val:.{nd}f}'

def ceil(a, b):
	ans = a // b
	if a % b != 0:
		ans += 1
	return ans

def perr(*args, **kwargs):
	if SLOW:
		print(*args, file=sys.stderr, **kwargs)

def line():
	ln = sys.stdin.readline().strip()
	if ln == '':
		sys.exit()
	return ln

def lines(n):
	return [line() for i in range(n)]

def split(ln=None):
	return (ln or line()).split()

def num(str=None):
	str = str or line()
	return float(str) if '.' in str else int(str)

def nums(o=None):
	if o is not None:
		if isinstance(o, int):
			o = lines(o)
		elif isinstance(o, str):
			o = split(o)
	return list(map(num, o or split()))

def mainloop(tcid=1):
	(n, k, d) = nums()

	@memoi
	def aaa(nn, dd=false):
		if nn == 0:
			return int(dd)
		ans = 0
		for xx in seq(1, min(nn, k)):
			aa = aaa(nn - xx, dd or xx >= d)
			ans = (ans + aa) % (10 ** 9 + 7)
		return ans
	ans = aaa(n)
	print(ans)
while tcid < tcmax:
	tcid += 1
	mainloop(tcid)


(n, k, d) = input().split()
(n, k, d) = (int(n), int(k), int(d))
ans1 = [0 for _ in range(101)]
ans1[0] = 1
ans = [0 for _ in range(101)]
for i in range(d):
	ans[i] = 0
for i in range(0, n + 1):
	j = 1
	while j <= k and i - j >= 0:
		ans1[i] += ans1[i - j]
		j += 1
for i in range(d, n + 1):
	j = 1
	while j <= k and i - j >= 0:
		if j >= d:
			ans[i] += ans1[i - j]
		else:
			ans[i] += ans[i - j]
		j += 1
print(ans[n] % 1000000007)


(n, k, d) = map(int, input().split())
f = [0] * (n + 1)
g = [1] * (n + 1)
d = 1 - d
m = 1000000007
for i in range(1, n + 1):
	f[i] = (sum((g[j] for j in range(max(0, i - k), d + i))) + sum((f[j] for j in range(max(0, d + i), i)))) % m
	g[i] = sum((g[j] for j in range(max(0, i - k), i))) % m
print(f[n])


MOD = 10 ** 9 + 7
(HAVE, NOT_HAVE) = (1, 0)
(n, k, d) = map(int, input().split())
dp = [[0 for _ in range(n + 1)] for _ in range(2)]
dp[NOT_HAVE][0] = 1
for dist in range(1, n + 1):
	for weight in range(1, k + 1):
		if weight > dist:
			break
		if weight >= d:
			dp[HAVE][dist] += dp[HAVE][dist - weight] + dp[NOT_HAVE][dist - weight]
			dp[HAVE][dist] %= MOD
		else:
			dp[NOT_HAVE][dist] += dp[NOT_HAVE][dist - weight]
			dp[NOT_HAVE][dist] %= MOD
			dp[HAVE][dist] += dp[HAVE][dist - weight]
			dp[HAVE][dist] %= MOD
print(dp[HAVE][n])


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def arr1d(n, v):
	return [v] * n

def arr2d(n, m, v):
	return [[v] * m for _ in range(n)]

def arr3d(n, m, p, v):
	return [[[v] * p for _ in range(m)] for i in range(n)]

def solve():
	(n, k, D) = sep()
	N = 10 ** 9 + 7

	@iterative
	def find1(ar, n):
		if n == 0:
			d[n] = 1
			yield 1
		elif n < 0:
			d[n] = 0
			yield 0
		elif d[n] != 0:
			yield d[n]
		s = 0
		for i in ar:
			yield find1(ar, n - i)
			s = (s + d[n - i]) % N
		d[n] = s
		yield s
	ar1 = list(range(1, k + 1))
	ar2 = list(range(1, D))
	d = defaultdict(int)
	a = find1(ar1, n)
	d = defaultdict(int)
	a -= find1(ar2, n)
	a %= N
	a = (a + N) % N
	print(a)
solve()


__author__ = 'epeshk'

def admod(a, b):
	a += b
	if a > 1000000000.0 + 7:
		a -= 1000000000.0 + 7
	return a
(n, k, d) = list(map(int, input().split()))
Dp = [[1, 0]]
for i in range(1, n + 1):
	Dp.append([0, 0])
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j < d:
			Dp[i][0] = admod(Dp[i][0], Dp[i - j][0])
			Dp[i][1] = admod(Dp[i][1], Dp[i - j][1])
		else:
			Dp[i][1] = admod(Dp[i][1], Dp[i - j][0])
			Dp[i][1] = admod(Dp[i][1], Dp[i - j][1])
print(int(Dp[n][1]))


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().strip()
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
from functools import lru_cache

@lru_cache(None)
def fun(n, k, d, d_taken=False, w=0):
	if n == 0 or w > n:
		return 0
	if w == n and d_taken:
		return 1
	ans = 0
	for i in range(1, d):
		ans += fun(n, k, d, d_taken, w=w + i)
		ans %= MOD
	for i in range(d, k + 1):
		ans += fun(n, k, d, True, w=w + i)
		ans %= MOD
	return ans % MOD
(n, k, d) = ilele()
print(fun(n, k, d) % MOD)


inputlist = list(map(int, input().split()))
n = inputlist[0]
k = inputlist[1]
d = inputlist[2]

def dp(sum1, limiter):
	array = [1] * 2
	if limiter == 0:
		return 0
	elif limiter == 1:
		return 1
	elif limiter == 2:
		for j in range(sum1 - 1):
			array.append(array[len(array) - 1] + array[len(array) - 2])
		return array[-1]
	elif sum1 > limiter:
		for j in range(1, limiter):
			array.append(2 ** j)
		leftpointer = 1
		rightpointer = limiter
		s = sum(array[1:])
		array.append(s)
		for j in range(sum1 - limiter - 1):
			s -= array[leftpointer]
			rightpointer += 1
			s += array[rightpointer]
			array.append(s)
			leftpointer += 1
		return array[-1]
	elif sum1 <= limiter:
		return 2 ** (sum1 - 1)
print((dp(n, k) - dp(n, d - 1)) % (10 ** 9 + 7))


dp = [0] * 101
dpx = [0] * 101
(n, k, d) = input().split()
n = int(n)
k = int(k)
d = int(d)
dp[0] = 1
dpx[0] = 1
for i in range(1, n + 1):
	for j in range(1, min(i, k) + 1):
		dp[i] = dp[i] + dp[i - j]
for i in range(1, n + 1):
	for j in range(1, min(i, d - 1) + 1):
		dpx[i] = dpx[i] + dpx[i - j]
print((dp[n] - dpx[n]) % 1000000007)


(n, k, d) = map(int, input().split())
a = [1]
b = [0]
for i in range(1, n + 1):
	a.append(sum(a[max(i - d + 1, 0):]))
	b.append(sum(a[max(i - k, 0):max(i - d + 1, 0)]) + sum(b[max(i - k, 0):]))
print(b[n] % 1000000007)


mod = 10 ** 9 + 7

def find(n, k, d):
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		j = i - 1
		c = 0
		s = 0
		while j >= 0 and c < k:
			s = (s + dp[j]) % mod
			j -= 1
			c += 1
		dp[i] = s
	return dp[-1]
(n, k, d) = map(int, input().split())
print((find(n, k, d) - find(n, d - 1, d)) % mod)


(n, k, d) = map(int, input().split())
MOD = int(1000000000.0 + 7)
dp = [[[0] * (n + 1) for i in range(n + 1)] for z in range(2)]
dp[0][0][0] = 1
res = 0
for i in range(1, n + 1):
	for s in range(1, n + 1):
		d0 = 0
		d1 = 0
		for v in range(1, min(d, s + 1)):
			d0 += dp[0][i - 1][s - v]
			d1 += dp[1][i - 1][s - v]
		for v in range(d, min(k + 1, s + 1)):
			d1 += dp[0][i - 1][s - v]
			d1 += dp[1][i - 1][s - v]
		dp[0][i][s] = d0 % MOD
		dp[1][i][s] = d1 % MOD
	res += dp[1][i][n]
print(res % MOD)


(aim, size, needed) = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
used = False
table_base = {}

def num_paths(used, curr):
	if (used, curr) in table_base:
		return table_base[used, curr]
	count = 0
	start_used = used
	for i in range(1, size + 1):
		if i == needed:
			used = True
		if curr + i < aim:
			count += num_paths(used, curr + i)
		elif curr + i == aim and used:
			count += 1
		else:
			break
	table_base[start_used, curr] = count
	return count
print(num_paths(used, 0) % mod)


import functools
(n, k, d) = map(int, input().split())
M = 10 ** 9 + 7

@functools.lru_cache(maxsize=None)
def f(n, k, d):
	if n <= 0:
		return 1 if n == 0 and d == 0 else 0
	ret = 0
	for i in range(1, k + 1):
		nd = 0 if i >= d else d
		ret = (ret + f(n - i, k, nd)) % M
	return ret
print(f(n, k, d))


(n, k, d) = map(int, input().split())
dp = [[0, 0] for j in range(n)]
for i in range(min(n, k)):
	dp[i][0] = 1
	if i >= d - 1:
		dp[i][1] = 1
for i in range(n):
	for j in range(max(0, i - k), i):
		dp[i][0] += dp[j][0]
		if i - j >= d:
			dp[i][1] += dp[j][0]
		else:
			dp[i][1] += dp[j][1]
print(dp[-1][-1] % (10 ** 9 + 7))


(n, k, d) = map(int, input().split())
a = [1]
b = [0]
for i in range(1, n + 1):
	a.append(sum(a[max(i - d + 1, 0):]))
	b.append(sum(a[max(i - k, 0):max(i - d + 1, 0)]) + sum(b[max(i - k, 0):]))
print(b[n] % (10 ** 9 + 7))


(n, k, d) = map(int, input().split())
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n + 1):
	for j in range(i - 1, -1, -1):
		if i - j > k:
			break
		if i - j < d:
			dp[i][0] += dp[j][0]
			dp[i][1] += dp[j][1]
		if i - j >= d and i - j <= k:
			dp[i][1] += dp[j][0] + dp[j][1]
print(dp[n][1] % (10 ** 9 + 7))


(n, k, d) = map(int, input().split())
N = 10 ** 9 + 7
matrix = [[0 for x1 in range(k + 1)] for x2 in range(n + 1)]
matrix[0][0] = 1
for s in range(0, n):
	for l in range(1, k + 1):
		if s + l > n:
			break
		for ml in range(0, k + 1):
			matrix[s + l][max(ml, l)] += matrix[s][ml]
			matrix[s + l][max(ml, l)] %= N
print(sum(matrix[-1][d:]) % N)


from functools import lru_cache

@lru_cache(maxsize=None)
def count_ways(n, k, d):
	if n == 0:
		return 1
	if n < d:
		return 0
	if n == d:
		return 1
	return sum((count_ways(n - i, k, d) for i in range(1, d))) + sum((count_ways(n - i, k, 1) for i in range(d, k + 1)))
(n, k, d) = map(int, input().split())
print(count_ways(n, k, d) % 1000000007)


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
st = [0] * (n + 1)
st[0] = 1
for j in range(1, n + 1):
	su = 0
	for i in range(max(0, j - k), j):
		su += st[i] % mod
	st[j] = su % mod
if d == 1:
	print(st[-1])
else:
	lst = [0] * (n + 1)
	lst[0] = 1
	for j in range(1, n + 1):
		su = 0
		for i in range(max(0, j - d + 1), j):
			su += lst[i] % mod
		lst[j] = su % mod
	print((st[-1] - lst[-1]) % mod)


memo = {}
(tg, k, d) = map(int, input().split())

def rec(n):
	if n in memo:
		return memo[n]
	ans = [0, 0]
	for b in range(1, min(k, n) + 1):
		if b == n:
			ans[b >= d] += 1
			continue
		r = rec(n - b)
		ans[1] += r[1]
		ans[b >= d] += r[0]
	memo[n] = ans
	return ans
print(rec(tg)[1] % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
(n, k, d) = map(int, input().split())
(dp, dp2) = ([0] * 105, [0] * 105)
(dp[0], dp2[0]) = (1, 1)
for i in range(1, n + 1):
	for j in range(max(0, i - k), i):
		dp[i] = (dp[i] + dp[j]) % MOD
	for j in range(max(0, i - d + 1), i):
		dp2[i] = (dp2[i] + dp2[j]) % MOD
print((dp[n] - dp2[n] + MOD) % MOD)


(f, k, d) = map(int, input().split())
a = [1]
b = [0]
mod = 1000000007
for i in range(1, f + 1):
	m = n = 0
	for j in range(1, k + 1):
		if i - j > 0 and j < d:
			m += a[i - j]
		elif i - j > 0 and j >= d:
			n += a[i - j]
		if i - j > 0:
			n += b[i - j]
	if i >= d and i <= k:
		n += 1
	elif i <= k:
		m += 1
	a.append(m % mod)
	b.append(n % mod)
print(b[f])


def dp(curr, least, k, total, loc=0):
	global d
	if curr == total:
		return int(least == 0)
	if d[curr][int(least == 0)] != -1:
		return d[curr][int(least == 0)]
	for i in range(1, k + 1):
		if curr + i > total:
			break
		loc += dp(curr + i, 0 if least <= i else least, k, total)
	d[curr][int(least == 0)] = loc % 1000000007
	return loc % 1000000007
(n, k, dd) = map(int, input().split())
d = [[-1, -1] for i in range(n)]
print(dp(0, dd, k, n))


import random
import sys
Q = 10 ** 9 + 7
(n, k, d) = map(int, input().split())
dp = [0] * 105
dp1 = [0] * 105
dp[0] = 1
dp1[0] = 1
for i in range(1, n + 1):
	for j in range(max(0, i - k), i):
		dp[i] = (dp[i] + dp[j]) % Q
	for j in range(max(0, i - d + 1), i):
		dp1[i] = (dp1[i] + dp1[j]) % Q
print((dp[n] - dp1[n] + Q) % Q)


from sys import stdin, stdout
(n, k, d) = stdin.readline().split()
n = int(n)
k = int(k)
d = int(d)
mod = 1000000007
wd = [0 for i in range(n + 1)]
wo = [0 for i in range(n + 1)]
wd[0] = 1
wo[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0:
			wd[i] += wd[i - j]
			wd[i] %= mod
for i in range(1, n + 1):
	for j in range(1, d):
		if i - j >= 0:
			wo[i] += wo[i - j]
			wo[i] %= mod
ans = (wd[n] - wo[n]) % mod
stdout.write(str(ans))


def read_line():
	return [int(i) for i in input().split(' ')]

def dp_calc(n, k, d):
	lim = 1000000007
	dist = [[1, 0]]
	for i in range(1, n + 1):
		s = [0, 0]
		for j in range(1, k + 1):
			if j > i:
				break
			if j < d:
				s[0] += dist[i - j][0]
				s[0] %= lim
				s[1] += dist[i - j][1]
				s[1] %= lim
			else:
				s[1] += dist[i - j][0]
				s[1] %= lim
				s[1] += dist[i - j][1]
				s[1] %= lim
		dist.append(s)
	return dist[n][1]
(n, k, d) = read_line()
r = dp_calc(n, k, d)
print(r)


from __future__ import division, print_function
import itertools, os, sys, threading
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from math import sqrt, floor, factorial, gcd, log
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations
from math import gcd
from bisect import bisect
input = lambda : sys.stdin.readline().rstrip('\r\n')
read = lambda : list(map(int, input().strip().split(' ')))

def main():
	(n, k, d) = read()
	dic = {}

	def func(required, f):
		key = str(required) + '-' + str(f)
		if key in dic:
			return dic[key]
		if required == 0:
			if f:
				return 1
			else:
				return 0
		if required < 0:
			return 0
		ans = 0
		for i in range(1, k + 1):
			ans += func(required - i, [f, 1][i >= d])
			ans %= 10 ** 9 + 7
		dic[key] = ans
		return ans
	print(func(n, 0))
main()


(n, k, d) = list(map(int, input().split()))

def get_ways(n, upper_bound):
	ways = [1] + [0] * n
	for i in range(1, n + 1):
		ways[i] = sum(ways[max(0, i - upper_bound):i])
	return ways[n]
print((get_ways(n, k) - get_ways(n, d - 1)) % (10 ** 9 + 7))


import math as mt
import sys, string
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
(n, k, d) = M()
3
dp = [0] * (n + 1)
dp[0] = 1
dp2 = [0] * (n + 1)
dp2[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0:
			dp[i] += dp[i - j]
for i in range(1, n + 1):
	for j in range(1, d):
		if i - j >= 0:
			dp2[i] += dp2[i - j]
print((dp[n] - dp2[n]) % (10 ** 9 + 7))


def solve(sums, c):
	if sums == 0:
		if c >= d:
			return True
		return False
	if sums < 0:
		return False
	if grid[sums][c] != -1:
		return grid[sums][c]
	temp = 0
	for i in range(1, k + 1):
		temp += solve(sums - i, max(i, c))
		temp = temp % mod
	grid[sums][c] = temp
	return temp
(n, k, d) = map(int, input().split())
mod = 1000000007
grid = [[-1 for i in range(n + 1)] for j in range(n + 1)]
print(solve(n, 0))


MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
[n, k, d] = list(map(int, input().split()))

def F(n, x):
	f = [1] + [0] * n
	for i in range(1, n + 1):
		f[i] = sum(f[max(i - x, 0):i])
	return f[n]
print((F(n, k) - F(n, d - 1)) % MOD)


(n, k, d) = map(int, input().split(' '))
dp = [[-1 for i in range(202)] for j in range(2002)]
mod = int(1000000007)

def f(_sum, ok):
	if dp[_sum][ok] == -1 and _sum < n:
		ans = 0
		for i in range(1, k + 1):
			if ok == 0 and i >= d:
				ans += f(_sum + i, 1)
			else:
				ans += f(_sum + i, ok)
			ans = ans % mod
		dp[_sum][ok] = ans
		return ans
	if dp[_sum][ok] != -1 and _sum < n:
		return dp[_sum][ok]
	if _sum == n and ok == 1:
		dp[_sum][ok] = 1
	if _sum > n:
		dp[_sum][ok] = 0
	if _sum == n and ok == 0:
		dp[_sum][ok] = 0
	return dp[_sum][ok]
print(f(0, 0))


def solve():
	(n, k, d) = get([int])
	mod = int(10 ** 9 + 7)

	@cache
	def foo(n, hasd):
		if n < 0:
			return 0
		if n == 0:
			if hasd:
				return 1
			else:
				return 0
		val = 0
		for i in range(1, k + 1):
			val += foo(n - i, True if i >= d else hasd)
		return val % mod
	ans = foo(n, False)
	return ans
_testcases = '\n3 3 2\n\n3\n\n\n\n\n3 3 3\n\n1\n\n\n\n\n4 3 2\n\n6\n\n\n\n\n4 5 2\n\n7\n'.strip()
from bisect import bisect_left, bisect_right
from functools import lru_cache
from heapq import heapify, heappop, heappush
from operator import itemgetter, attrgetter
import bisect
import collections
import functools
import heapq
import itertools
import math
import operator
import re
import string
import sys
inf = float('inf')
cache = lru_cache(None)
sys.setrecursionlimit(10000)

def printRecursionTree(func):
	return func

def tree():
	return collections.defaultdict(tree)

def equal(x, y, epsilon=1e-06):
	if -epsilon <= x - y <= epsilon:
		return True
	if -epsilon <= x <= epsilon or -epsilon <= y <= epsilon:
		return False
	return -epsilon <= (x - y) / x <= epsilon or -epsilon <= (x - y) / y <= epsilon

def get(_type):
	if type(_type) == list:
		if len(_type) == 1:
			_type = _type[0]
			return list(map(_type, input().strip().split()))
		else:
			return [_type[i](inp) for (i, inp) in enumerate(input().strip().split())]
	else:
		return _type(input().strip())
(_p, print) = (print, lambda *a, **b: None)
_p(solve())


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bs(a, l, h, x):
	while l < h:
		mid = (l + h) // 2
		if a[mid] == x:
			return mid
		if a[mid] < x:
			l = mid + 1
		else:
			h = mid
	return l

def sieve(a):
	for i in range(3, 10 ** 6 + 1, 2):
		a[i] = 1
	for i in range(3, 10 ** 6 + 1, 2):
		for j in range(i * i, 10 ** 6 + 1, i):
			a[j] = 0
	a[2] = 1
	return a

def solve():
	(n, k, d) = sep()
	coin = []
	for i in range(1, k + 1):
		coin.append(i)
	dp1 = [0] * (n + 1)
	dp2 = [0] * (n + 1)
	dp1[0] = 1
	for i in range(1, n + 1):
		for c in coin:
			if i - c >= 0:
				if c >= d:
					dp2[i] += dp2[i - c]
					dp2[i] += dp1[i - c]
				else:
					dp2[i] += dp2[i - c]
					dp1[i] += dp1[i - c]
	print(dp2[n] % mod)
testcase(1)


def numWays(n, k):
	if k == 0:
		return 0
	s = [1] * (n + 1)
	for i in range(2, min(k + 1, n + 1)):
		s[i] = s[i - 1] << 1
	for i in range(k + 1, n + 1):
		s[i] = (s[i - 1] << 1) - s[i - k - 1]
	return s[n]

def solve():
	(n, k, d) = map(int, input().split())
	mod = 1000000007
	print((numWays(n, k) - numWays(n, d - 1)) % mod)
solve()


(n, k, d) = list(map(int, input().split()))
dct = {}

def getPaths(s, k, got, d):
	global dct
	tot = 0
	try:
		tot = dct[s, k, got, d]
		return tot
	except:
		pass
	for x in range(1, k + 1):
		if x == s:
			if got or x >= d:
				tot += 1
			break
		elif x < s:
			if x >= d:
				tot += getPaths(s - x, k, True, d)
			else:
				tot += getPaths(s - x, k, got, d)
	dct[s, k, got, d] = tot
	return tot
total = getPaths(n, k, False, d)
print(total % 1000000007)


mem = [[-1, -1] for x in range(0, 103)]
(n, k, d) = list(map(int, input().split()))

def dp(remain, has_d):
	if remain == 0:
		return has_d
	if remain < 0:
		return 0
	if mem[remain][has_d] != -1:
		return mem[remain][has_d]
	mem[remain][has_d] = 0
	for i in range(1, min(remain, k) + 1):
		if i >= d:
			mem[remain][has_d] += dp(remain - i, 1)
		else:
			mem[remain][has_d] += dp(remain - i, has_d)
	return mem[remain][has_d]
print(dp(n, 0) % (10 ** 9 + 7))


import sys
inf = float('inf')
(mod, MOD) = (1000000007, 998244353)

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, k, d) = get_ints()
w = [0] * (n + 1)
wot = [0] * (n + 1)
for i in range(1, n + 1):
	if i <= k:
		w[i] = 1
		if i < d:
			wot[i] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			continue
		w[i] = (w[i] + w[i - j]) % mod
		if j < d:
			wot[i] = (wot[i] + wot[i - j]) % mod
print((w[n] - wot[n] + mod) % mod)


mod = int(1000000000.0 + 7)
(n, k, d) = map(int, input().split())
dp = [0 for i in range(n + k + 1)]
dp[0] = 1
for i in range(n + 1):
	for j in range(1, k + 1):
		dp[i + j] += dp[i]
dp2 = [0 for i in range(n + k + 1)]
dp2[0] = 1
for i in range(n + 1):
	for j in range(1, d):
		dp2[i + j] += dp2[i]
print((dp[n] - dp2[n]) % mod)


def prog():
	(n, k, d) = map(int, input().split())
	mod = 10 ** 9 + 7
	ways = [0 for i in range(n + 1)]
	for i in range(1, min(k + 1, n + 1)):
		ways[i] = 1
	for i in range(1, n + 1):
		for j in range(max(1, i - k), i):
			ways[i] += ways[j]
	ways_less_d = [0 for i in range(n + 1)]
	k = d - 1
	for i in range(1, min(k + 1, n + 1)):
		ways_less_d[i] = 1
	for i in range(1, n + 1):
		for j in range(max(1, i - k), i):
			ways_less_d[i] += ways_less_d[j]
	print((ways[n] - ways_less_d[n]) % mod)
prog()


import functools
_MODER = 1000000007

def solve(n, k, d):

	@functools.lru_cache(None)
	def find_not_yet_d(n):
		if n < d:
			return 0
		r = 0
		for i in range(1, min(n, k) + 1):
			if i >= d:
				r += find_used_d(n - i)
			else:
				r += find_not_yet_d(n - i)
		return r % _MODER

	@functools.lru_cache(None)
	def find_used_d(n):
		if n == 0:
			return 1
		r = 0
		for i in range(1, min(n, k) + 1):
			r += find_used_d(n - i)
		return r % _MODER
	return find_not_yet_d(n) % _MODER
(n, k, d) = map(int, input().split())
print(solve(n, k, d))


mod = 1000000000.0 + 7
(n, k, d) = map(int, input().split())
dic = [[0 for i in range(2)] for j in range(n + 1)]
dic[0][0] = 1
dic[0][1] = 0
for i in range(1, n + 1):
	j = 1
	while j <= k and i - j >= 0:
		if j < d:
			dic[i][0] += dic[i - j][0]
			dic[i][0] %= mod
			dic[i][1] += dic[i - j][1]
			dic[i][1] %= mod
		if j >= d:
			dic[i][1] += dic[i - j][0]
			dic[i][1] %= mod
			dic[i][1] += dic[i - j][1]
			dic[i][1] %= mod
		j += 1
print(int(dic[n][1]))


P = 1000000007
A = [1]
B = [0]
(n, k, d) = map(int, input().split())
for i in range(n):
	S1 = 0
	S2 = 0
	for j in range(k):
		if j <= i:
			S1 = (S1 + A[i - j]) % P
			if j >= d - 1:
				S2 = (S2 + A[i - j]) % P
			else:
				S2 = (S2 + B[i - j]) % P
	A.append(S1)
	B.append(S2)
print(B[n])


import sys
mod = 1000000007
get_arr = lambda : list(map(int, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()

def fn(n, k, d, flag, cache, mod):
	if n == 0 and flag:
		return 1
	if n == 0 and (not flag):
		return 0
	if n < 0:
		return 0
	key = (n, flag)
	if key in cache:
		return cache[key]
	ans = 0
	for i in range(1, k + 1):
		if i >= d:
			ans += fn(n - i, k, d, True, cache, mod)
		else:
			ans += fn(n - i, k, d, flag, cache, mod)
		if ans >= mod:
			ans %= mod
	cache[key] = ans
	return ans
(n, k, d) = get_ints()
print(fn(n, k, d, False, {}, mod))


inputs = [int(x) for x in input().split()]
desired_weight = inputs[0]
k = inputs[1]
min_weight = inputs[2]
saved = [{True: None, False: None} for i in range(desired_weight + 1)]
saved[desired_weight] = {True: 0, False: 0}
modulo = 1000000007
for i in reversed(range(0, desired_weight)):
	range_to_work_with = i + k
	hit_min_value = 0
	fail_to_hit_min_value = 0
	travel_range = range(i + 1, i + k + 1 if i + k + 1 <= desired_weight + 1 else desired_weight + 1)
	for j in travel_range:
		if j - i >= min_weight:
			fail_to_hit_min_value += saved[j][True]
		else:
			fail_to_hit_min_value += saved[j][False]
	fail_to_hit_min_value += 1 if desired_weight - i <= k and desired_weight - i >= min_weight else 0
	for j in travel_range:
		hit_min_value += saved[j][True]
	hit_min_value += 1 if desired_weight - i <= k else 0
	saved[i][True] = hit_min_value
	saved[i][False] = fail_to_hit_min_value
print(saved[0][False] % modulo)


(n, k, d) = list(map(int, input().split()))
f = [0] * (n + k + 1)
f_ = [0] * (n + k + 1)
f_[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		f[i] += f[i - j]
	for j in range(d, k + 1):
		f[i] += f_[i - j]
	for j in range(1, d):
		f_[i] += f_[i - j]
print(f[n] % (10 ** 9 + 7))


def main():
	(n, k, d) = map(int, input().split())
	mod = 10 ** 9 + 7
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i >= j:
				dp[i] += dp[i - j] % mod
			else:
				break
		dp[i] = dp[i] % mod
	if d == 1:
		print(dp[n])
	else:
		dpl = [0] * (n + 1)
		dpl[0] = 1
		for i in range(1, n + 1):
			for j in range(1, d):
				if i >= j:
					dpl[i] += dpl[i - j]
			dpl[i] = dpl[i] % mod
		print((dp[n] - dpl[n]) % mod)
main()


mod = 1000000000.0 + 7

def Sulution():
	(n, k, d) = [int(x) for x in input().split()]
	dp = [[0 for i in range(2)] for j in range(101)]
	dp[0][0] = 1
	dp[0][1] = 0
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i < j:
				break
			if j < d:
				dp[i][0] += dp[i - j][0]
				dp[i][0] %= mod
				dp[i][1] += dp[i - j][1]
				dp[i][1] %= mod
			else:
				dp[i][1] += dp[i - j][0]
				dp[i][1] %= mod
				dp[i][1] += dp[i - j][1]
				dp[i][1] %= mod
	return int(dp[n][1])
print(Sulution())


m = 1000000000.0 + 7

def add_mod(numb: int, ways: int) -> int:
	numb += ways
	if numb >= m:
		return int(numb % m)
	return numb
(n, k, d) = map(int, input().split())
a = [[0] * 2 for i in range(n + 1)]
a[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j < d:
			a[i][0] = add_mod(a[i][0], a[i - j][0])
			a[i][1] = add_mod(a[i][1], a[i - j][1])
		else:
			a[i][1] = add_mod(a[i][1], a[i - j][0])
			a[i][1] = add_mod(a[i][1], a[i - j][1])
print(a[n][1])


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
add = [0] * 105
sub = [0] * 105
add[0] = sub[0] = 1
for i in range(n + 1):
	for p in range(min(n - i, k)):
		add[p + i + 1] = (add[p + i + 1] + add[i]) % mod
	for q in range(min(n - i, d - 1)):
		sub[q + i + 1] = (sub[q + i + 1] + sub[i]) % mod
print((add[n] - sub[n] + mod) % mod)


(n, k, d) = map(int, input().split())
dp = {}
vis = []

def F(curr, poss):
	if curr < 0:
		return 0
	if curr == 0 and poss == 1:
		return 1
	if (curr, poss) in vis:
		return dp[curr, poss]
	i = 1
	vis.append((curr, poss))
	dp[curr, poss] = 0
	while i < d:
		dp[curr, poss] += F(curr - i, poss)
		i += 1
	i = d
	while i <= k:
		dp[curr, poss] += F(curr - i, 1)
		i += 1
	return dp[curr, poss] % 1000000007
print(F(n, 0))


def dp(n, k, d, f, m):
	if n == 0:
		if f == True:
			return 1
		return 0
	if n < 0:
		return 0
	if m[n][f] != -1:
		return m[n][f]
	res = 0
	for i in range(1, k + 1):
		if i >= d:
			res += dp(n - i, k, d, f | True, m)
		else:
			res += dp(n - i, k, d, f | False, m)
	m[n][f] = res % 1000000007
	return m[n][f]
(n, k, d) = [int(x) for x in input().split()]
m = [[-1, -1] for _ in range(n + 1)]
print(dp(n, k, d, False, m))


MOD = 1000000007
(n, k, d) = map(int, input().split())
count = [[0] * (n + 1) for i in range(2)]
count[0][0] = 1
for nn in range(1, n + 1):
	for i in range(1, min(k + 1, nn + 1)):
		count[0][nn] += count[0][nn - i]
		count[0][nn] %= MOD
	for i in range(1, min(d, nn + 1)):
		count[1][nn] += count[1][nn - i]
		count[1][nn] %= MOD
	for i in range(d, min(k + 1, nn + 1)):
		count[1][nn] += count[0][nn - i]
		count[1][nn] %= MOD
print(count[1][n])


def add_self(i, j, x):
	dp[i][j] += dp[x][j]
	if dp[i][j] > m:
		dp[i][j] -= m
(n, k, d) = map(int, input().split())
m = 1000000007
dp = [[[0, 1][i == 1 and j != 0] for j in range(k + 1)] for i in range(n + 1)]
for i in range(2, n + 1):
	for j in range(1, k + 1):
		if i <= j:
			dp[i][j] = (1 << i - 1) % m
		else:
			for x in range(i - j, i):
				add_self(i, j, x)
print((dp[n][k] - dp[n][d - 1]) % m)


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	(n, k, d) = read_tuple(int)
	edges = [i for i in range(1, k + 1)]
	cnt_normal = [0 for _ in range(n + 1)]
	cnt_d = [0 for _ in range(n + 1)]
	for i in range(1, n + 1):
		for edge in edges:
			if i == edge:
				cnt_normal[i] += 1
				if edge < d:
					cnt_d[i] += 1
			if i - edge >= 0:
				cnt_normal[i] += cnt_normal[i - edge]
				if edge < d:
					cnt_d[i] += cnt_d[i - edge]
	print((cnt_normal[n] - cnt_d[n]) % 1000000007)
solve()


import logging
import sys
nivel_log = logging.ERROR
logger_cagada = None

def kk_tree_core(n, k, d):
	dp = [0] * (n + 1)
	dp_grande = [0] * (n + 1)
	dp[0] = 1
	dp_grande[0] = 1
	num_formas = 0
	for tam_casilla in range(1, n - d + 1):
		logger_cagada.debug('en tam casilla {}'.format(tam_casilla))
		for num_act in range(1, d):
			if num_act > tam_casilla:
				break
			resto = tam_casilla - num_act
			logger_cagada.debug('num act {} resto {}'.format(num_act, resto))
			dp[tam_casilla] += dp[resto]
	logger_cagada.debug('la dp es {}'.format(dp))
	dp[0] = 0
	for tam_casilla in range(d, n + 1):
		logger_cagada.debug('el tam casilla g {}'.format(tam_casilla))
		for num_act in range(1, k + 1):
			if num_act > tam_casilla:
				break
			resto = tam_casilla - num_act
			if resto < d and num_act < d:
				continue
			logger_cagada.debug('num act g {} resto {}'.format(num_act, resto))
			num_formas_chicas = dp[resto] if num_act >= d else 0
			num_formas_grandes = dp_grande[resto]
			logger_cagada.debug('num formas chicas {} grandes {}'.format(num_formas_chicas, num_formas_grandes))
			dp_grande[tam_casilla] += num_formas_chicas + num_formas_grandes
	logger_cagada.debug('la dp grande  es {}'.format(dp_grande))
	num_formas = dp_grande[n]
	return num_formas % 1000000007

def kk_tree_main():
	lineas = list(sys.stdin)
	(n, k, d) = [int(x) for x in lineas[0].strip().split(' ')]
	resu = kk_tree_core(n, k, d)
	print('{}'.format(resu))
FORMAT = '[%(filename)s:%(lineno)s - %(funcName)20s() ] %(message)s'
logging.basicConfig(level=nivel_log, format=FORMAT)
logger_cagada = logging.getLogger('asa')
logger_cagada.setLevel(nivel_log)
kk_tree_main()


mod = 10 ** 9 + 7

def solve(n, k):
	dp = [0] * 101
	if k <= 0:
		return 0
	for i in range(1, k + 1):
		dp[i] = 1
	for i in range(1, n + 1):
		for j in range(1, min(k + 1, i)):
			dp[i] = dp[i] + dp[i - j]
			dp[i] = dp[i] % mod
	return dp[n]
mod = 10 ** 9 + 7
a = list(map(int, input().split()))
q = solve(a[0], a[1]) - solve(a[0], a[2] - 1)
q = (mod + q) % mod
print(q)


(n, k, d) = list(map(int, input().split()))
dict1 = {}
for i in range(1, n + 1):
	str1 = str(i) + '_' + '1' + '_' + '1'
	dict1[str1] = i
for i in range(1, k + 1):
	str1 = '1' + '_' + str(i) + '_' + '1'
	dict1[str1] = 1

def solve(n, k, d, z):
	str1 = str(n) + '_' + str(k) + '_' + str(d)
	if n == 0 or n == d:
		return 1
	if d > k or n < 0 or d > n:
		return 0
	if str1 in dict1.keys():
		return dict1[str1]
	else:
		ans = 0
		for i in range(k, d - 1, -1):
			ans += solve(n - i, k, 1, z)
			ans %= z
		for j in range(1, d):
			ans += solve(n - j, k, d, z)
			ans %= z
		dict1[str1] = ans
		return ans
z = 10 ** 9 + 7
print(solve(n, k, d, z))


import sys
import math
input = sys.stdin.readline

def inlt():
	return list(map(int, input().split()))

def helper(rem, found):
	if rem == 0:
		if found:
			return 1
		return 0
hash_map = {}

def solve(n, found):
	if n == 0:
		if found:
			return 1
		return 0
	if (n, found) in hash_map:
		return hash_map[n, found]
	count = 0
	for i in range(1, k + 1):
		if i > n:
			break
		count += solve(n - i, found | (True if i >= d else False)) % 1000000007
	hash_map[n, found] = count % 1000000007
	return count % 1000000007
nkd = inlt()
(k, d) = (nkd[1], nkd[2])
print(int(solve(nkd[0], False)))


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for i in range(n + 1)]
dp[0][0] = 1
for su in range(n + 1):
	for mi in range(k + 1):
		for i in range(1, k + 1):
			if su + i <= n:
				dp[su + i][max(i, mi)] += dp[su][mi] % mod
print(int(sum(dp[n][d:]) % mod))


import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
import math
(inf, floor, ceil) = (math.inf, math.floor, math.ceil)
from collections import defaultdict, Counter, deque
from functools import lru_cache, reduce
from bisect import bisect, bisect_left
from heapq import heapify, heappush, heappop, heappushpop
from itertools import permutations, combinations, product
mod = 10 ** 9 + 7
eps = 1e-05

def print_arr(arr):
	n = len(arr)
	for i in range(n - 1):
		stdout.write(str(arr[i]) + ' ')
	stdout.write(str(arr[-1]) + '\n')

def solve(n, k, d):

	@lru_cache(None)
	def dp(n, in_path):
		if n == 0:
			return 1 if in_path else 0
		if n < 0:
			return 0
		ans = 0
		for i in range(1, k + 1):
			if i >= d:
				in_path = True
			ans = (ans + dp(n - i, in_path)) % mod
		return ans
	return dp(n, False)
t = 1
for _ in range(t):
	line = stdin.readline()
	(n, k, d) = map(int, line.split(' '))
	print(solve(n, k, d))


MODULO = int(1000000000.0) + 7

def findnumways(n, d_state, k, d, num_ways):
	if n < 0:
		return 0
	if n == 0 and (not d_state):
		return 0
	if n == 0 and d_state:
		return 1
	if (n, d_state) in num_ways:
		return num_ways[n, d_state]
	cnt = 0
	for i in range(1, k + 1):
		if i < d:
			cnt += findnumways(n - i, False or d_state, k, d, num_ways) % MODULO
		else:
			cnt += findnumways(n - i, True, k, d, num_ways) % MODULO
	num_ways[n, d_state] = cnt % MODULO
	return cnt % MODULO
(n, k, d) = map(int, input().split())
num_ways = dict()
print(findnumways(n, False, k, d, num_ways) % MODULO)


(n, k, d) = map(int, input().split())
dp = [[-1, -1] for j in range(101)]
m = 10 ** 9 + 7

def ans(n, t):
	global d, m, k
	if dp[n][t] >= 0:
		return dp[n][t]
	if n == d and t == 0:
		return 1
	if n < d and t == 0:
		return 0
	if n == 0:
		return 1
	c = 0
	for i in range(1, d):
		if n >= i:
			c += ans(n - i, t)
			c %= m
	for i in range(d, k + 1):
		if n >= i:
			c += ans(n - i, 1)
			c %= m
	dp[n][t] = c % m
	return c % m
print(ans(n, 0))


(n, k, d) = map(int, input().split())
l1 = [0]
for i in range(1, n + 1):
	if i <= k:
		l1.append(2 ** (i - 1))
	else:
		l1.append(sum(l1[i - k:i]))
l2 = [0]
for i in range(1, n + 1):
	if i <= d - 1:
		l2.append(2 ** (i - 1))
	else:
		l2.append(sum(l2[i - d + 1:i]))
print((l1[n] - l2[n]) % (10 ** 9 + 7))


(n, k, d) = map(int, input().split())
M = 10 ** 9 + 7
dp = [[0 for i in range(2)] for j in range(n + 1)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0:
			dp[i][1] = (dp[i][1] + dp[i - j][1]) % M
			if j >= d:
				dp[i][1] = (dp[i][1] + dp[i - j][0]) % M
			else:
				dp[i][0] = (dp[i][0] + dp[i - j][0]) % M
print(dp[n][1])


import sys
import math as mt
mod = 1000000007
t = 1
for __ in range(t):
	(n, k, d) = map(int, input().split())
	ans = 0
	cnt = []
	for i in range(1, k + 1):
		cnt.append(i)
	cnt1 = []
	for i in range(1, d):
		cnt1.append(i)
	ways = [0] * (n + 1)
	ways[0] = 1
	for i in range(1, n + 1):
		for j in range(len(cnt)):
			if cnt[j] <= i:
				ways[i] = (ways[i] % mod + ways[i - cnt[j]] % mod) % mod
	ways1 = [0] * (n + 1)
	ways1[0] = 1
	for i in range(1, n + 1):
		for j in range(len(cnt1)):
			if cnt1[j] <= i:
				ways1[i] = (ways1[i] % mod + ways1[i - cnt1[j]] % mod) % mod
	print((ways[n] - ways1[n]) % mod)


def sums(n, k, d, dic):
	count = 0
	limited_count = 0
	for i in range(1, k + 1):
		if n - i == 0:
			count += 1
			if n >= d:
				limited_count += 1
		elif n - i < 0:
			pass
		else:
			count += dic[n - i][0]
			if i >= d:
				limited_count += dic[n - i][0]
			else:
				limited_count += dic[n - i][1]
	return (count % (10 ** 9 + 7), limited_count % (10 ** 9 + 7))

def tree(n, k, d):
	dic = {}
	for i in range(1, n + 1):
		dic[i] = sums(i, k, d, dic)
	return dic[n][1]
lst = list(map(lambda elem: int(elem), input().split(' ')))
print(tree(lst[0], lst[1], lst[2]))


from sys import stdin, stdout
from math import sqrt
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, input().split()))
M = 10 ** 9 + 7
for _ in range(1):
	(n, k, d) = lst()
	dp = [[0 for i in range(d + 1)] for _ in range(n + 1)]
	for i in range(n + 1):
		for j in range(d + 1):
			if i == j == 0:
				dp[i][j] = 1
			elif j > i:
				dp[i][j] = 0
			else:
				for eu in range(1, k + 1):
					if i - eu >= 0:
						dp[i][j] = (dp[i][j] + dp[i - eu][0 if eu >= j else j]) % M
	print(dp[n][d] % M)


tree = list(map(int, input('').split(' ')))
(n, k, d) = (tree[0], tree[1], tree[2])
dp = [[0 for i in range(2)] for j in range(n + 1)]
dp[0][0] = 1
dp[0][1] = 0
mod = 1000000007
for i in range(1, n + 1):
	dp[i][0] = 0
	dp[i][1] = 0
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j >= d:
			dp[i][1] += dp[i - j][0]
			dp[i][1] += dp[i - j][1]
		else:
			dp[i][0] += dp[i - j][0]
			dp[i][1] += dp[i - j][1]
print(dp[n][1] % mod)


input_ = list(map(int, input().split()))
(n, k, d) = (input_[0], input_[1], input_[2])
dp = [['None' for i in range(d + 1)] for j in range(n + 1)]
for j in range(d + 1):
	dp[0][j] = 0
	for i in range(n + 1):
		if j > i:
			dp[i][j] = 0
	if dp[1][j] == 'None':
		dp[1][j] = 1
	for i in range(min(d + 1, n + 1)):
		if dp[i][i] == 'None':
			dp[i][i] = 1
for n_temp in range(1, n + 1):
	for d_temp in range(d + 1):
		if dp[n_temp][d_temp] == 'None':
			dp[n_temp][d_temp] = sum([dp[n_temp - i][((d_temp - i) * (i >= d_temp) + d_temp * (i < d_temp)) * ((d_temp - i) * (i >= d_temp) + d_temp * (i < d_temp) >= 0)] for i in range(1, min([k + 1, n_temp + 1]))]) + (n_temp <= k)
print(dp[n][d] % (10 ** 9 + 7))


(n, k, d) = [int(x) for x in input().split()]
z = [[1], [1]]
for i in range(1, n + 1):
	z[0].append(sum(z[0][max(i - d + 1, 0):]))
	z[1].append(sum(z[1][max(i - k, 0):]))
print((z[1][-1] - z[0][-1]) % (10 ** 9 + 7))


(n, k, d) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = {}

def rec(remaining, flag=False):
	if remaining < 0:
		return 0
	if remaining == 0 and flag == True:
		return 1
	if (remaining, flag) in dp:
		return dp[remaining, flag]
	ans = 0
	for i in range(1, k + 1):
		if i <= remaining:
			ans += rec(remaining - i, flag | (i >= d))
			ans %= MOD
	dp[remaining, flag] = ans
	return ans
ans = rec(n) % MOD
print(ans)


(n, k, d) = map(int, input().split())
mod = 1000000007
memo = [[-1] * 100 for i in range(n + 1)]

def dp(nn, s):
	sum1 = 0
	if nn == 0:
		if s == 0:
			return 0
		else:
			return 1
	if memo[nn][s] != -1:
		return memo[nn][s]
	for i in range(1, min(k, nn) + 1):
		sum1 = (sum1 % mod + dp(nn - i, 1 if s == 1 or i >= d else 0) % mod) % mod
	memo[nn][s] = sum1
	return sum1
r = dp(n, 0)
print(r)


(n, k, d) = map(int, input().split())
dp1 = [0] * 10000
dp2 = [0] * 10000
dp1[0] = 1
dp2[0] = 1
MOD = 1000 * 1000 * 1000 + 7
for i in range(n):
	for j in range(1, k + 1):
		dp1[i + j] += dp1[i]
		dp1[i + j] %= MOD
	for j in range(1, d):
		dp2[i + j] += dp2[i]
		dp2[i + j] %= MOD
if d > n:
	print(0)
else:
	print(int((dp1[n] - dp2[n]) % MOD))


MOD = 1000000007
(n, k, d) = map(int, input().split())
if d > n:
	print(0)
else:
	dp = [[0, 0] for x in range(n + 1)]
	(dp[0][0], dp[0][1]) = (1, 0)
	for sm in range(1, n + 1):
		till = min(d - 1, sm)
		for weight in range(1, till + 1):
			dp[sm][0] += dp[sm - weight][0] % MOD
			dp[sm][1] += dp[sm - weight][1] % MOD
		for weight in range(till + 1, min(sm, k) + 1):
			dp[sm][1] += dp[sm - weight][0] % MOD
			dp[sm][1] += dp[sm - weight][1] % MOD
	print(dp[sm][1] % MOD)


(n, k, d) = map(int, input().split())
mat = [1]
less = [1]
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	mat.append(sum(mat[max(i - d + 1, 0):]))
	less.append(sum(less[max(i - k, 0):]))
print((less[-1] - mat[-1]) % mod)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, k, d) = ria()
		coins = [int(x) for x in range(1, k + 1)]
		x = n
		dp = [0] * 1000005
		dp[0] = 1
		mod = int(1000000000.0) + 7
		for i in range(1, x + 1):
			for j in coins:
				if j - i > 0:
					break
				dp[i] = (dp[i] + dp[i - j]) % mod
		total = dp[x]
		coins = [int(x) for x in range(1, d)]
		x = n
		dp = [0] * 1000005
		dp[0] = 1
		mod = int(1000000000.0) + 7
		for i in range(1, x + 1):
			for j in coins:
				if j - i > 0:
					break
				dp[i] = (dp[i] + dp[i - j]) % mod
		waste = dp[x]
		print((total - waste) % mod)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


M = 10 ** 9 + 7
(n, k, d) = map(int, input().split())
dp = [[0, 0] for i in range(n + 1)]
for i in range(1, min(n, d)):
	dp[i][0] = 1
for i in range(d, min(n + 1, k + 1)):
	dp[i][1] = 1
for i in range(1, n + 1):
	zero = dp[i][0]
	for j in range(i - 1, max(0, i - d), -1):
		zero += dp[j][0]
		zero %= M
	dp[i][0] = zero
	one = dp[i][1]
	for j in range(i - 1, max(0, i - k - 1), -1):
		one += dp[j][1]
		one %= M
	for j in range(max(0, i - d), max(0, i - k - 1), -1):
		one += dp[j][0]
		one %= M
	dp[i][1] = one
print(dp[n][-1])


def k_tree(n, k, d, suma, flag, memo):
	if suma > n:
		return 0
	if suma == n:
		if flag == 1:
			return 1
		else:
			return 0
	if memo[suma][flag] != -1:
		return memo[suma][flag]
	aux = 0
	for i in range(1, k + 1):
		aux += k_tree(n, k, d, suma + i, 1 if i >= d else flag, memo)
		aux %= 1000000007
	memo[suma][flag] = aux
	return memo[suma][flag]
(n, k, d) = map(int, input().split())
memo = [[-1 for i in range(2)] for i in range(n)]
print(k_tree(n, k, d, 0, 0, memo))


(n, k, d) = map(int, input().split())

def mod(x):
	if x >= 10 ** 9 + 7:
		return x - (10 ** 9 + 7)
	return x
dp = [[0, 0] for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0:
			if j < d:
				dp[i][0] += dp[i - j][0]
				dp[i][1] += dp[i - j][1]
				dp[i][0] = mod(dp[i][0])
				dp[i][1] = mod(dp[i][1])
			else:
				dp[i][1] += dp[i - j][0]
				dp[i][1] = mod(dp[i][1])
				dp[i][1] += dp[i - j][1]
				dp[i][1] = mod(dp[i][1])
print(dp[n][1])


(n, k, d) = map(int, input().split(' '))
dp = [[0, 0] for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j < d:
			dp[i][0] += dp[i - j][0] % 1000000007
			dp[i][1] += dp[i - j][1] % 1000000007
		else:
			dp[i][1] += dp[i - j][0] % 1000000007
			dp[i][1] += dp[i - j][1] % 1000000007
print(dp[n][1] % 1000000007)


(n, k, d) = map(int, input().split())
dp = [[0 for i in range(3)] for j in range(101)]
(dp[0][0], dp[0][1]) = (1, 0)
md = 10 ** 9 + 7
for i in range(1, n + 1):
	dp[i][0] = dp[i][1] = 0
	for j in range(1, k + 1):
		if i < j:
			break
		if j < d:
			dp[i][0] = (dp[i][0] + dp[i - j][0]) % md
			dp[i][1] = (dp[i][1] + dp[i - j][1]) % md
		else:
			dp[i][1] = (dp[i][1] + dp[i - j][0]) % md
			dp[i][1] = (dp[i][1] + dp[i - j][1]) % md
print(dp[n][1])


from __future__ import print_function
import math
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
(n, k, d) = invr()
sum = [0] * 101
for i in range(d - 1):
	sum[i] = 1
for j in range(101):
	for i in range(1, d):
		if j + 1 - i > 0:
			sum[j] = (sum[j] + sum[j + 1 - i - 1]) % mod
s1 = [0] * 101
for i in range(k):
	s1[i] = 1
for j in range(101):
	for i in range(1, k + 1):
		if j + 1 - i > 0:
			s1[j] = (s1[j] + s1[j + 1 - i - 1]) % mod
print((s1[n - 1] - sum[n - 1] + mod) % mod)


def solve(n, k, d):
	dp = []
	modulo = 1000000007
	for i in range(n + 1):
		dp.append([0] * (n + 1))
	dp[0][0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j < 0:
				break
			if j < d:
				dp[i][0] = (dp[i][0] + dp[i - j][0]) % modulo
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % modulo
			else:
				dp[i][1] = (dp[i][1] + dp[i - j][0]) % modulo
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % modulo
	return dp[n][1]

def main():
	(n, k, d) = list(map(int, input().split()))
	print(solve(n, k, d))
main()


MOD = 10 ** 9 + 7

def calculate(n, max_k):
	if max_k == 0:
		return 0
	dp = [0] * (n + 1)
	dp[1] = 1
	for i in range(2, n + 1):
		m = min(i - 1, max_k)
		if i <= max_k:
			dp[i] += 1
		for j in range(1, m + 1):
			dp[i] += dp[i - j]
			dp[i] = dp[i] % MOD
	return dp[-1]
(n, k, d) = list(map(int, input().split()))
if d > n:
	print(0)
elif d == n:
	print(1)
else:
	total = calculate(n, k)
	no_d = calculate(n, d - 1)
	total -= no_d
	if total < 0:
		total += MOD
	print(total)


import itertools
I = lambda : map(int, input().split())
(n, k, d) = I()
levels = [{0: [1, 0]}]
for i in range(n):
	levels.append({})
	for (w_0, w_d) in itertools.product(levels[-2], range(1, k + 1)):
		w_1 = w_0 + w_d
		if w_1 > n:
			continue
		if w_1 not in levels[-1]:
			levels[-1][w_1] = [0, 0]
		if w_d >= d:
			levels[-1][w_1][1] += sum(levels[-2][w_0])
		else:
			levels[-1][w_1][0] += levels[-2][w_0][0]
			levels[-1][w_1][1] += levels[-2][w_0][1]
ans = 0
for l in levels:
	if n in l:
		ans += l[n][1]
print(ans % 1000000007)


(total_weight, children, at_least_one) = [int(x) for x in input().split()]
at_least_weights = [0] * (total_weight + 1)
not_least_weights = [0] * (total_weight + 1)
if total_weight < at_least_one:
	print(0)
elif total_weight == at_least_one:
	print(1)
else:
	not_least_weights[0] = 1
	for x in range(1, total_weight + 1):
		for y in range(1, at_least_one):
			if x - y >= 0:
				not_least_weights[x] += not_least_weights[x - y]
				at_least_weights[x] += at_least_weights[x - y]
		for z in range(at_least_one, children + 1):
			if x - z >= 0:
				at_least_weights[x] += at_least_weights[x - z]
				at_least_weights[x] += not_least_weights[x - z]
	print(at_least_weights[total_weight] % 1000000007)


import collections

def count(n, k):
	m = collections.defaultdict(lambda : 0)
	m[0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j in m:
				m[i] += m[i - j]
	return m[n]
(n, k, d) = tuple(map(int, str.split(input())))
print((count(n, k) - count(n, d - 1)) % (10 ** 9 + 7))


dp1 = [0] * 101
dp2 = [0] * 101
(n, k, d) = map(int, input().split())
for i in range(1, k + 1):
	dp1[i] = 1
	if i < d:
		dp2[i] = 1
dp1[0] = 0
dp2[0] = 0
m = 10 ** 9 + 7
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i > j:
			dp1[i] = (dp1[i] + dp1[i - j]) % m
			if j < d:
				dp2[i] = (dp2[i] + dp2[i - j]) % m
print((dp1[n] - dp2[n]) % m)


def read_input():
	line = input().strip().split()
	n = int(line[0])
	k = int(line[1])
	d = int(line[2])
	print(calculate(n, k, d, {}) % (10 ** 9 + 7))

def calculate(n, k, d, memo):
	if (n, d) in memo:
		return memo[n, d]
	else:
		if (n, d) == (0, 0):
			return 1
		x = 0
		for i in range(1, min(k, n) + 1):
			if i >= d:
				x += calculate(n - i, k, 0, memo)
			elif n >= i + d:
				x += calculate(n - i, k, d, memo)
		memo[n, d] = x
		return x
read_input()


(n, k, d) = input().split()
(n, k, d) = (int(n), int(k), int(d))
mod = 10 ** 9 + 7
dp = [1]
for i in range(1, n + 1):
	if i == 1:
		dp.append(1)
	else:
		dp.append(0)
		for j in range(1, min(k, i) + 1):
			dp[-1] += dp[i - j]
		dp[-1] %= mod
DP = [0]
for i in range(1, n + 1):
	if i < d:
		DP.append(0)
	else:
		DP.append(0)
		for j in range(1, min(k, i) + 1):
			if j < d:
				DP[-1] += DP[i - j]
			else:
				DP[-1] += dp[i - j]
		DP[-1] %= mod
print(DP[-1])


(n, k, d) = map(int, input().split())
kp = [-1] * (n + 1)

def CP(m):
	global k
	if m == 0:
		return 1
	if kp[m] != -1:
		return kp[m]
	c = 0
	for t in range(1, min(m, k) + 1):
		c += CP(m - t)
		c = c % 1000000007
	kp[m] = c
	return c
kc = [-1] * (n + 1)

def CP2(m):
	global d
	if m == 0:
		return 1
	if kc[m] != -1:
		return kc[m]
	c = 0
	for t in range(1, min(m, d - 1) + 1):
		c += CP2(m - t)
		c = c % 1000000007
	kc[m] = c
	return c
print((CP(n) - CP2(n)) % 1000000007)


cache = [-1] * 102
cache_d = [-1] * 102
cache_d[0] = 1
(n, k, d) = map(int, input().split(' '))
for i in range(d):
	cache[i] = 0

def rec_d(n):
	if n < 0:
		return 0
	if cache_d[n] < 0:
		res = 0
		for i in range(1, k + 1):
			res += rec_d(n - i)
		cache_d[n] = res % 1000000007
	return cache_d[n]

def rec(n):
	if n < 0:
		return 0
	if cache[n] < 0:
		res = 0
		for i in range(1, d):
			res += rec(n - i)
		for i in range(d, k + 1):
			res += rec_d(n - i)
		cache[n] = res % 1000000007
	return cache[n]
print(rec(n))


(n, k, d) = input().strip().split()
n = int(n)
k = int(k)
d = int(d)
dp = [0 for i in range(102)]
dp[0] = 1
p = [0 for i in range(102)]
p[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j < 0:
			break
		dp[i] = (dp[i] + dp[i - j]) % 1000000007
	for j in range(1, d):
		if i - j < 0:
			break
		p[i] = (p[i] + p[i - j]) % 1000000007
print(((dp[n] - p[n]) % 1000000007 + 1000000007) % 1000000007)


dp = {}

def find(n, k, d, curr=0, flag=False):
	state = tuple([curr, flag])
	if state in dp:
		return dp[state]
	if curr == n:
		return 1 if flag else 0
	ways = 0
	for i in range(1, k + 1):
		if curr + i <= n:
			curr_flag = flag
			if i >= d:
				curr_flag = True
			ways += find(n, k, d, curr + i, curr_flag)
	dp[curr, flag] = ways
	return ways

def solve(n, k, d):
	big = float('inf')
	small = float('-inf')
	return find(n, k, d) % (10 ** 9 + 7)

def main():
	d = input()
	d = [int(i) for i in d.split()]
	a = d[0]
	b = d[1]
	c = d[2]
	ans = solve(a, b, c)
	print(ans)
main()


(n, k, d) = map(int, input().split())
dp0 = [0] * (n + 1)
dp0[0] = 1
dp1 = [0] * (n + 1)
for i in range(1, n + 1):
	j = 1
	while k >= j:
		if i - j < 0:
			break
		if j < d:
			dp0[i] += dp0[i - j]
			dp1[i] += dp1[i - j]
		else:
			dp1[i] += dp0[i - j]
			dp1[i] += dp1[i - j]
		j += 1
print(dp1[-1] % 1000000007)


temp = list(map(int, input().split()))
(n, k, d) = (temp[0], temp[1], temp[2])
mod = 1000000007
dp = [[0, 0] for _ in range(n + 1)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	for j in range(1, min(i, k) + 1):
		if j < d:
			dp[i][0] += dp[i - j][0] % mod
			dp[i][1] += dp[i - j][1] % mod
		else:
			dp[i][1] += dp[i - j][0] % mod
			dp[i][1] += dp[i - j][1] % mod
print(dp[n][1] % mod)


(n, k, d) = map(int, input().strip().split(' '))
dp = [0] * (n + k + 1)
vp = [0] * (n + k + 1)
for i in range(1, n + 1):
	for j in range(1, k + 1):
		dp[i] += dp[i - j]
		if j >= d:
			continue
		else:
			vp[i] += vp[i - j]
	if i <= k:
		dp[i] += 1
		if i >= d:
			continue
		else:
			vp[i] += 1
print((dp[n] - vp[n]) % (10 ** 9 + 7))


mod = 1000000007
d = []
for _ in range(101):
	d.append([0, 0])

def add(a, b):
	a += b
	if a >= mod:
		a -= mod
	return a
(n, k, h) = map(int, input().split())
d[0][0] = 1
d[0][1] = 0
for i in range(1, n + 1):
	d[i][0] = d[i][1] = 0
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j < h:
			d[i][0] = add(d[i][0], d[i - j][0])
			d[i][1] = add(d[i][1], d[i - j][1])
		else:
			d[i][1] = add(d[i][1], d[i - j][0])
			d[i][1] = add(d[i][1], d[i - j][1])
print(d[n][1])


(n, k, d) = map(int, input().split(' '))
a = [0] * (n + 1)
b = [0] * (n + 1)
a[0] = 1
b[0] = 1
m = 1000000007
for i in range(1, n + 1):
	a[i] = 0
	b[i] = 0
	j = 1
	while j <= k and i - j >= 0:
		a[i] = a[i] + a[i - j]
		j = j + 1
	j = 1
	while j < d and i - j >= 0:
		b[i] = b[i] + b[i - j]
		j = j + 1
print((a[n] % m - b[n] % m) % m)


(n, k, d) = [int(x) for x in input().split()]
mod = 1000000000.0 + 7
a = [[None for _ in range(2)] for _ in range(n + 1)]
a[0][0] = 1
a[0][1] = 0
for i in range(1, n + 1):
	a[i][0] = 0
	a[i][1] = 0
	for j in range(1, k + 1):
		if j > i:
			break
		if j < d:
			a[i][0] = (a[i][0] + a[i - j][0]) % mod
		else:
			a[i][1] = (a[i][1] + a[i - j][0]) % mod
		a[i][1] = (a[i][1] + a[i - j][1]) % mod
print(int(a[n][1]))


def k_tree(n, k, d):

	def _k_tree(n, k):
		if k <= 0 or n <= 0:
			return 0
		cache = [1] * n
		for i in range(1, n):
			sum_num = 0
			for j in range(max(0, i - k), i):
				sum_num += cache[j]
			if i < k:
				sum_num += 1
			cache[i] = sum_num
		return cache[-1]
	return _k_tree(n, k) - _k_tree(n, d - 1)
(n, k, d) = map(int, input().strip().split())
print(k_tree(n, k, d) % 1000000007)


import sys
sys.setrecursionlimit(1500)

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
arr = get_ints()
n = arr[0]
k = arr[1]
d = arr[2]
dicts = {}
ans = 0

def dfs(v, flag):
	strs = str(v) + ',' + str(flag)
	if strs in dicts:
		return dicts[strs]
	if v > n:
		dicts[strs] = 0
		return 0
	if v == n and flag == 1:
		dicts[strs] = 1
		return 1
	if v == n:
		dicts[strs] = 0
		return 0
	temp = 0
	for i in range(1, k + 1):
		if i >= d:
			flag = 1
		temp += dfs(i + v, flag)
	dicts[strs] = temp
	return temp % 1000000007
for i in range(1, k + 1):
	flag = 0
	if i >= d:
		flag = 1
	if i == n and flag == 1:
		ans += 1
		break
	if i == n and flag == 0:
		break
	if i > n:
		break
	dfs(i, flag)
	strs = str(i) + ',' + str(flag)
	ans += dicts[strs]
	ans = ans % 1000000007
print(ans % 1000000007)


(n, k, d) = map(int, input().split())
M = 1000000007

def solve(n, k):
	if k == 0:
		return 0
	ans = [0] * (n + 1)
	for i in range(1, min(n + 1, k + 1)):
		ans[i] = 1
	for i in range(1, n + 1):
		ans[i] = sum(ans[max(1, i - k):i + 1]) % M
	return ans[n]
print((solve(n, k) - solve(n, d - 1)) % M)


from __future__ import print_function
import sys
from collections import *
from heapq import *
from functools import *
INF = float('inf')
NINF = float('-inf')
try:
	input = raw_input
except:
	pass

def read_string():
	return input()

def read_int_line():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())

class TreeNode(object):

	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

	def __str__(self):
		q = deque()
		ans = []
		q.append(self)
		ans.append(self.val)
		while q:
			cur = q.popleft()
			ans.append(cur.left.val if cur.left else 'null')
			ans.append(cur.right.val if cur.right else 'null')
			if cur.left:
				q.append(cur.left)
			if cur.right:
				q.append(cur.right)
		while ans and ans[-1] == 'null':
			ans.pop()
		return str(ans).replace("'null'", 'null')

def toTreeNode(s):
	l = eval(s.replace('null', 'None'))
	n = len(l)
	if not n:
		return None
	root = TreeNode(l[0])
	q = deque()
	q.append(root)
	i = 1
	while q and i < n:
		cur = q.popleft()
		if l[i] != None:
			cur.left = TreeNode(l[i])
			q.append(cur.left)
		i += 1
		if i >= n:
			break
		if l[i] != None:
			cur.right = TreeNode(l[i])
			q.append(cur.right)
		i += 1
	return root

class Djs:

	def __init__(self, n):
		self.w = [1] * n
		self.p = [-1] * n

	def find(self, x):
		p = self.p[x]
		if p == -1:
			return x
		else:
			self.p[x] = self.find(p)
			return self.p[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return
		if self.w[x] > self.w[y]:
			(x, y) = (y, x)
		self.p[x] = y
		self.w[y] += self.w[x]

	def roots(self):
		return [x for (x, y) in enumerate(self.p) if y == -1]

def mat3d(x, y, z, fill=0):
	return [[[fill] * z for _ in range(y)] for _ in range(x)]

def mat2d(h, w, fill=0):
	return [[fill] * w for _ in range(h)]

def matmul(m1, m2, P=0):
	(h1, w1) = (len(m1), len(m1[0]))
	(h2, w2) = (len(m2), len(m2[0]))
	assert w1 == h2
	ans = mat2d(h1, w2)
	if P:
		for i in range(h1):
			for j in range(w2):
				for k in range(w1):
					ans[i][j] = (ans[i][j] + m1[i][k] * m2[k][j]) % P
	else:
		for i in range(h1):
			for j in range(w2):
				for k in range(w1):
					ans[i][j] = ans[i][j] + m1[i][k] * m2[k][j]
	return ans

def mati(n):
	ans = mat2d(n, n)
	for i in range(n):
		ans[i][i] = 1
	return ans

def matpow(m, p, P):
	(h, w) = (len(m), len(m[0]))
	assert h == w
	ans = mati(h)
	base = m
	while p:
		if p % 2 == 1:
			ans = matmul(ans, base, P)
		base = matmul(base, base, P)
		p //= 2
	return ans

def doit():
	(n, k, d) = read_int_line()
	dp = mat2d(n + 1, 2, 0)
	dp[0][0] = 1
	P = 10 ** 9 + 7
	for ni in range(1, n + 1):
		for cur in range(1, min(k + 1, ni + 1)):
			if cur < d:
				dp[ni][0] += dp[ni - cur][0]
				dp[ni][1] += dp[ni - cur][1]
			else:
				dp[ni][1] += dp[ni - cur][0] + dp[ni - cur][1]
		dp[ni][0] %= P
		dp[ni][1] %= P
	print('%d' % dp[n][1])
try:
	while True:
		doit()
except EOFError:
	pass


(n, k, d) = map(int, input().split())
dp = [[0 for i in range(2)] for j in range(n + 10)]
dp[0][0] = 1
MOD = int(1000000000.0) + 7
for i in range(1, n + 1):
	for j in range(1, min(d - 1, n) + 1):
		dp[i][0] += dp[i - j][0] % MOD
	for j in range(1, min(d - 1, n) + 1):
		dp[i][1] += dp[i - j][1] % MOD
	for j in range(d, min(n, k) + 1):
		dp[i][1] += (dp[i - j][0] + dp[i - j][1]) % MOD
print(dp[n][1] % MOD)


def backtrack(visited, sum, included):
	global res
	if sum == 0:
		flag7 = 0
		for a in visited:
			if a >= d:
				flag7 = 1
				break
		if flag7 == 1:
			res += 1
			print(visited)
			return
		return
	if sum < 0:
		return
	for a in range(1, k + 1):
		visited.append(a)
		backtrack(visited, sum - a, included)
		visited.pop()
(n, k, d) = map(int, input().strip().split())
dp = [1]
for a in range(1, n + 1):
	s = 0
	for b in range(max(0, a - k), a):
		s += dp[b]
	dp.append(s)
dp1 = [1]
for a in range(1, n + 1):
	s = 0
	for b in range(max(0, a - d + 1), a):
		s += dp1[b]
	dp1.append(s)
print((dp[-1] - dp1[-1]) % (10 ** 9 + 7))


def w(N, K):
	a = [0] * (N + 1)
	a[0] = 1
	d = 1
	i = 1
	while i <= min(N, K):
		a[i] = d
		d += a[i]
		i += 1
	if N > K:
		x = K + 1
		while x <= N:
			a[x] = sum(a[x - K:x])
			x += 1
	return a[-1]

def sol():
	(n, k, g) = map(int, input().split(' '))
	result = (w(n, k) - w(n, g - 1)) % (10 ** 9 + 7)
	print(result)
sol()


ans = {}

def gen(n, k, d, used=False):
	if not ans.get((n, k, d, used)):
		if not n and used:
			ans[n, k, d, used] = 1
		else:
			ans[n, k, d, used] = sum((gen(n - x, k, d, used or x >= d) for x in range(1, min(n, k) + 1) if max(x, n - x) >= d or used))
	return ans[n, k, d, used]
(n, k, d) = list(map(int, input().split()))
print(gen(n, k, d) % 1000000007)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(int(pow(10, 6)))
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(n, k, d) = l()
dp1 = [0 for i in range(n + 1)]
dp2 = [0 for i in range(n + 1)]
dp1[0] = 1
dp2[0] = 1
K = [i for i in range(1, k + 1)]
D = [i for i in range(1, d)]
for i in range(n):
	for c in K:
		if i + c >= n + 1:
			break
		dp1[i + c] += dp1[i]
for i in range(n):
	for c in D:
		if i + c >= n + 1:
			break
		dp2[i + c] += dp2[i]
print((dp1[-1] - dp2[-1]) % mod)


def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
M = 10 ** 9 + 7

def solve():
	(N, K, D) = getInts()
	dp = [[0 for j in range(2)] for i in range(N + 1)]
	dp[0][0] = 1
	for i in range(1, N + 1):
		for j in range(1, min(K + 1, N + 1)):
			if j < D:
				dp[i][0] += dp[i - j][0]
				dp[i][1] += dp[i - j][1]
			else:
				dp[i][1] += dp[i - j][0]
				dp[i][1] += dp[i - j][1]
			dp[i][0] %= M
			dp[i][1] %= M
	return dp[N][1]
ans = solve()
print(ans)


(n, k, d) = map(int, input().split())

def recurse(n, d, dp={}):
	if n == d:
		return 1
	if (n, d) not in dp:
		dp[n, d] = sum((recurse(n - i, d if i < d else 0) for i in range(1, min(n + 1, k + 1)))) % 1000000007
	return dp[n, d]
print(recurse(n, d))


(n, k, d) = map(int, input().split())
k = n if n < k else k
cnt = [0 for _ in range(n + 1)]
cn = [0 for _ in range(n + 1)]
cnt[0] = cn[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i >= j:
			cnt[i] += cnt[i - j]
		if i >= j and j < d:
			cn[i] += cn[i - j]
s1 = cnt[n]
s2 = cn[n]
print((s1 - s2) % 1000000007)


inp = input().split()
n = int(inp[0])
k = int(inp[1])
d = int(inp[2])
if n < d:
	print(0)
else:
	D = [[0 for i in range(n + 1)], [0 for j in range(n + 1)]]
	D[0][0] = 0
	D[1][0] = 0
	for j in range(n):
		if j + 1 <= k and d <= j + 1:
			D[1][j + 1] = 1
		elif j + 1 <= k and d > j + 1:
			D[0][j + 1] = 1
		for i in range(d - 1):
			if j - i - 1 >= 0:
				D[1][j + 1] += D[1][j - i]
				D[0][j + 1] += D[0][j - i]
			else:
				break
		for i in range(k - d + 1):
			if j + 1 - d - i >= 0:
				D[1][j + 1] += D[1][j + 1 - i - d] + D[0][j + 1 - i - d]
			else:
				break
	print(D[1][n] % 1000000007)


MOD = 1000000007
(n, k, d) = map(int, input().split())
dp = [0 for i in range(n + 1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
	for j in range(max(0, i - k), i):
		dp[i] += dp[j]
dp2 = [0 for i in range(n + 1)]
dp2[0] = 1
dp2[1] = 1
for i in range(2, n + 1):
	for j in range(max(0, i - d + 1), i):
		dp2[i] += dp2[j]
ans = dp[n] - dp2[n]
if n == 1 and d <= 1:
	ans = 1
if ans > MOD:
	ans = ans % MOD
print(ans)


import sys
(n, k, d) = map(int, sys.stdin.readline().split())
dp = [0] * (n + 1)
dp1 = [0] * (n + 1)
dp[0] = dp1[0] = 1
mod = 1000000007
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		dp[i] += dp[i - j]
for i in range(1, n + 1):
	for j in range(1, d):
		if i < j:
			break
		dp1[i] += dp1[i - j]
print((dp[n] - dp1[n]) % mod)


def solve(s):
	(n, k, d) = list(map(int, s.split()))
	return int((dp(n, k) - dp(n, d - 1)) % 1000000007)

def dp(n, k):
	l = [2 ** i for i in range(k)]
	while len(l) < n:
		l.append(sum(l[-k:]))
	return l[n - 1]
s = input()
print(solve(s))


import functools
import sys
p = 10 ** 9 + 7
line = input()
tokens = line.split()
(n, k, d) = (int(tokens[0]), int(tokens[1]), int(tokens[2]))

@functools.lru_cache(None)
def f(s):
	if s == 0:
		return 1
	total = 0
	for w in range(1, k + 1):
		if w > s:
			break
		total += f(s - w)
	return total % p

@functools.lru_cache(None)
def g(s):
	if s == 0:
		return 1
	total = 0
	for w in range(1, min(d, k + 1)):
		if w > s:
			break
		total += g(s - w)
	return total % p
print((f(n) - g(n)) % p)


(n, k, d) = map(int, input().split())
mat = [1]
sat = [1]
for i in range(1, n + 1):
	mat.append(sum(mat[max(i - d + 1, 0):]))
	sat.append(sum(sat[max(i - k, 0):]))
print((sat[-1] - mat[-1]) % 1000000007)


import math
from collections import defaultdict, Counter, deque
MOD = int(1000000000.0) + 7
(n, k, d) = map(int, input().split())
dp = [[0, 0] for i in range(n + 1)]
dp[0] = [1, 1]
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0 and dp[i - j]:
			dp[i][0] = (dp[i][0] + dp[i - j][0]) % MOD
			if j >= d:
				dp[i][1] = (dp[i][1] + dp[i - j][0]) % MOD
			elif i - j >= d:
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % MOD
print(dp[n][1])


(n, k, d) = map(int, input().split())
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)
dp1[0] = 1
for i in range(1, n + 1):
	for j in range(1, min(n, k) + 1):
		dp2[i] += dp2[i - j]
		if j < d:
			dp1[i] += dp1[i - j]
		else:
			dp2[i] += dp1[i - j]
print(dp2[n] % 1000000007)


(N, K, D) = [int(i) for i in input().split()]
M = 100
T = [[0] * (M + 1), [0] * (M + 1)]
for k in range(1, K + 1):
	T[k >= D][k] = 1
for n in range(1, M + 1):
	for k in range(1, K + 1):
		if n + k > M:
			continue
		T[1][n + k] += T[1][n]
		T[k >= D][n + k] += T[0][n]
print(T[1][N] % 1000000007)


from sys import stdin, stdout
input = stdin.readline

def print(x):
	stdout.write(str(x) + '\n')
mod = 10 ** 9 + 7

def solve():
	l = list(map(int, input().split()))
	(n, k, d) = l
	dp = [[0] * 2 for i in range(n + 1)]
	dp[0][0] = 1
	dp[0][1] = 0
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i < j:
				break
			if j >= d:
				dp[i][1] += (dp[i - j][0] + dp[i - j][1]) % mod
				dp[i][1] %= mod
			else:
				dp[i][0] = (dp[i][0] + dp[i - j][0]) % mod
				dp[i][1] = (dp[i][1] + dp[i - j][1]) % mod
	print(dp[n][1])
t = 1
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline

def inInt():
	return int(input())

def inStr():
	return input().strip('\n')

def inIList():
	return list(map(int, input().split()))

def inSList():
	return input().split()

def bsearch(nums, target):
	N = len(nums or [])
	l = 0
	r = N - 1
	while l <= r:
		mid = (l + r) // 2
		if nums[mid] < target:
			l = mid + 1
		elif nums[mid] > target:
			r = mid - 1
		else:
			return (None, mid, None)
	return (r if r >= 0 else None, None, l if l <= N - 1 else None)

def yesOrNo(val):
	print('YES' if val else 'NO')

def printSpacedArray(nums):
	print(*nums)
(n, k, d) = inIList()
dp = [[0 for i in range(2)] for i in range(101)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	dp[i][0] = 0
	dp[i][1] = 0
	for j in range(1, k + 1):
		if j > i:
			break
		if j < d:
			dp[i][0] += dp[i - j][0]
			dp[i][1] += dp[i - j][1]
			dp[i][0] %= 1000000007
			dp[i][1] %= 1000000007
		else:
			dp[i][1] += dp[i - j][0]
			dp[i][1] += dp[i - j][1]
			dp[i][1] %= 1000000007
print(dp[n][1])


from array import *

def kTree(n, a, d):
	dp = {}
	i = 0
	while i <= n:
		dp[0, i] = 0
		dp[1, i] = 1
		i += 1
	i = 2
	while i <= a:
		dp[i, 0] = 1
		j = 1
		while j <= n:
			if i > j:
				dp[i, j] = dp[i - 1, j]
			elif i == j:
				dp[i, j] = (dp[i - 1, j] + dp[i, 0]) % 1000000007
			else:
				l = i
				dp[i, j] = 0
				while l > 0:
					dp[i, j] = (dp[i, j] + dp[i, j - l]) % 1000000007
					l -= 1
			j += 1
		i += 1
	print((dp[k, n] - dp[d - 1, n]) % 1000000007)
(n, k, d) = [int(x) for x in input().split()]
kTree(n, k, d)


mod = 10 ** 9 + 7

def countWays(arr, m, N, d):
	count = [0 for i in range(N + 1)]
	count[0] = 1
	for i in range(1, N + 1):
		for j in range(m):
			if i >= arr[j] and arr[j] < d:
				count[i] += count[i - arr[j]]
			count[i] %= mod
	return count[N]

def countWays1(arr, m, N):
	count = [0 for i in range(N + 1)]
	count[0] = 1
	for i in range(1, N + 1):
		for j in range(m):
			if i >= arr[j]:
				count[i] += count[i - arr[j]]
		count[i] %= mod
	return count[N]
(n, k, d) = map(int, input().split())
a = [i for i in range(1, k + 1)]
t1 = countWays(a, len(a), n, d)
t2 = countWays1(a, len(a), n)
print((t2 - t1 + mod) % mod)


(n, k, d) = input().split()
n = int(n)
k = int(k)
d = int(d)
c = [0] * (n + 1)
fs = [0] * (n + 1)
fs[0] = 0
c[0] = 1
for i in range(1, n + 1):
	for j in range(1, min(n, k) + 1):
		fs[i] += fs[i - j]
		if j < d:
			c[i] += c[i - j]
		else:
			fs[i] += c[i - j]
print(fs[n] % 1000000007)


mod = 10 ** 9 + 7
path = [[-1] * 2 for _ in range(101)]

def count(i, state):
	if path[i][state] != -1:
		return path[i][state]
	if i == 0:
		return state
	result = 0
	for j in range(1, k + 1):
		if i >= j:
			result = (result + count(i - j, [1, state][j < d])) % mod
	path[i][state] = result
	return path[i][state]
(n, k, d) = map(int, input().split())
print(count(n, 0))


mod = 10 ** 9 + 7

def ktree(l, a, dp, k, d):
	if l < 0:
		return 0
	if l == 0 and a == 0:
		return 0
	if l == 0 and a == 1:
		return 1
	if dp[l][a] != -1:
		return dp[l][a]
	sum = 0
	for i in range(1, k + 1):
		if i >= d:
			sum += ktree(l - i, 1, dp, k, d)
		else:
			sum += ktree(l - i, a, dp, k, d)
	dp[l][a] = sum
	return dp[l][a]
s = str(input())
l = s.split()
n = int(l[0])
k = int(l[1])
d = int(l[2])
dp = [[-1 for i in range(2)] for i in range(101)]
print(ktree(n, 0, dp, k, d) % mod)


mod = 1000000007
(n, k, d) = map(int, input().split())
arr = []
for i in range(n + 1):
	t = [0, 0]
	arr.append(t)
if n < d:
	print(0)
else:
	arr[1][0] = 1
	arr[d][1] = 1
	if d == 1:
		arr[1][0] = 0
	for i in range(2, n + 1):
		temp = 0
		if i < d:
			temp += 1
		for j in range(i - 1, max(0, i - d), -1):
			temp += arr[j][0]
			temp %= mod
		arr[i][0] = temp
	for i in range(d + 1, n + 1):
		temp = 0
		for j in range(i - 1, max(d - 1, i - k - 1), -1):
			temp += arr[j][1]
			temp %= mod
		if i <= k:
			temp += 1
			temp %= mod
		for j in range(i - d, max(0, i - k - 1), -1):
			temp += arr[j][0]
			temp %= mod
		arr[i][1] = temp
	print(arr[n][1] % mod)


(n, k, d) = input().split()
n = int(n)
k = int(k)
d = int(d)
dp = [0] * (n + 1)
s = [0] * (n + 1)
dp[0] = 1
s[0] = 1
if n < d:
	print(0)
else:
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if j <= i:
				dp[i] = dp[i] + dp[i - j]
		for j in range(1, d):
			if j <= i:
				s[i] = s[i] + s[i - j]
	sum1 = 0
	for i in range(n - d + 1, n):
		sum1 += s[i]
	print((dp[n] - sum1) % 1000000007)


(n, k, d) = list(map(int, input().split()))

def paths_with_weight(n, k, d):
	if n == 0:
		return 1 if d == 0 else 0
	if n < 0:
		return 0
	return sum([paths_with_weight(n - i, k, d if i < d else 0) for i in range(1, k + 1)])

def dp_paths_with_weight(n, k, d, modulo=0):
	P = [[0 for b in range(2)] for i in range(n + 1)]
	P[0][0] = 1
	if modulo:
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if i - j >= 0:
					P[i][0] += P[i - j][0] % modulo
					P[i][1] += (P[i - j][1] if j < d else P[i - j][0]) % modulo
		return P[n][1] % modulo
	else:
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if i - j >= 0:
					P[i][0] += P[i - j][0]
					P[i][1] += P[i - j][1] if j < d else P[i - j][0]
		return P[n][1]
print(dp_paths_with_weight(n, k, d, 1000000007))


import os
import sys
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def seive(n):
	primes = [True] * (n + 1)
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	return primes

def factors(n):
	factors = []
	x = 2
	while x * x <= n:
		while n % x == 0:
			factors.append(x)
			n //= x
		if n > 1:
			factors.append(x)
	return factors

def main():
	try:
		(n, k, d) = invr()
		mod = int(1000000000.0 + 7)
		dp = [[0, 0] for _ in range(101)]
		dp[0][0] = 1
		dp[0][1] = 0
		for i in range(1, n + 1):
			dp[i][0] = dp[i][1] = 0
			for j in range(1, k + 1):
				if i - j < 0:
					break
				if j < d:
					dp[i][0] += dp[i - j][0]
					dp[i][0] %= mod
					dp[i][1] += dp[i - j][1]
					dp[i][1] %= mod
				else:
					dp[i][1] += dp[i - j][0]
					dp[i][1] %= mod
					dp[i][1] += dp[i - j][1]
					dp[i][1] %= mod
		print(dp[n][1])
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import itertools, functools, math
MOD = 1000000007

@functools.lru_cache(None)
def dp(n, k, d, d_used=False):
	if n == d and (not d_used):
		return 1
	if n == 0:
		return 1
	if n < d and (not d_used):
		return 0
	r = 0
	for i in range(1, min(n + 1, k + 1)):
		r = (r + dp(n - i, k, d, d_used or i >= d)) % MOD
	return r

def solve():
	(n, k, d) = map(int, input().split())
	return dp(n, k, d)
print(solve())


def w(N, K):
	a = [0] * (N + 1)
	a[0] = 1
	for i in range(1, min(N, K) + 1):
		a[i] = sum(a[0:i])
	if N > K:
		for x in range(K + 1, N + 1):
			a[x] = sum(a[x - K:x])
	return a[-1]

def sol():
	(n, k, g) = map(int, input().split(' '))
	result = (w(n, k) - w(n, g - 1)) % (10 ** 9 + 7)
	print(result)
sol()


(n, k, d) = map(int, input().split())
M = 1000000007
a = [1] + [0] * n
for i in range(1, n + 1):
	for j in range(max(0, i - k), i):
		a[i] = (a[i] + a[j]) % M
b = [1] + [0] * n
for i in range(1, n + 1):
	for j in range(max(0, i - d + 1), i):
		b[i] = (b[i] + b[j]) % M
print((a[n] - b[n]) % M)


def solve(n, k, d, e, memo):
	if n < 0:
		return 0
	if n == 0:
		return e
	if (n, e) in memo:
		return memo[n, e]
	ans = 0
	for i in range(1, d):
		ans += solve(n - i, k, d, e, memo)
	for i in range(d, k + 1):
		ans += solve(n - i, k, d, 1, memo)
	memo[n, e] = ans % 1000000007
	return ans % 1000000007
(n, k, d) = (int(x) for x in input().split())
print(solve(n, k, d, 0, dict()))


(n, k, d) = map(int, input().split())
dp = [0 for x in range(n + 1)]
dp[0] = 1
for i in range(1, n + 1):
	for j in range(1, min(k, i) + 1):
		dp[i] += dp[i - j]
dp1 = [0 for x in range(n + 1)]
dp1[0] = 1
for i in range(1, n + 1):
	for j in range(1, min(d - 1, i) + 1):
		dp1[i] += dp1[i - j]
print((dp[n] - dp1[n]) % 1000000007)


MOD = 10 ** 9 + 7
(n, k, d) = [int(x) for x in input().split()]
include = [0 for i in range(n + 1)]
exclude = [0 for i in range(n + 1)]
for i in range(n + 1):
	if i <= k:
		include[i] = 1
		if i < d:
			exclude[i] = 1
include[0] = exclude[0] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			continue
		include[i] += include[i - j] % MOD
		if j < d:
			exclude[i] += exclude[i - j] % MOD
print((include[n] - exclude[n]) % MOD)


(n, k, d) = map(int, input().split())
dp = [[0 for j in range(2)] for i in range(101)]
dp[0][1] = 1
for i in range(1, n + 1):
	for j in range(1, min(i, k) + 1):
		if j >= d:
			dp[i][0] = (dp[i][0] + dp[i - j][1]) % int(1000000000.0 + 7)
		else:
			dp[i][0] = (dp[i][0] + dp[i - j][0]) % int(1000000000.0 + 7)
		dp[i][1] = (dp[i][1] + dp[i - j][1]) % int(1000000000.0 + 7)
print(dp[n][0])


(n, k, d) = [int(x) for x in input().split()]
klist = [0 for i in range(101)]
dminusonelist = [0 for i in range(101)]
twopower = 1
for i in range(1, k + 1):
	klist[i] = twopower
	twopower = twopower * 2 % 1000000007
twopower = 1
for i in range(1, d):
	dminusonelist[i] = twopower
	twopower = twopower * 2 % 1000000007
for i in range(k + 1, 101):
	thesum = 0
	for j in range(i - k, i):
		thesum = (thesum + klist[j]) % 1000000007
	klist[i] = thesum
for i in range(d, 101):
	thesum = 0
	for j in range(i - d + 1, i):
		thesum = (thesum + dminusonelist[j]) % 1000000007
	dminusonelist[i] = thesum
if d == 1:
	print(klist[n])
else:
	tempanswer = klist[n] - dminusonelist[n]
	if tempanswer < 0:
		tempanswer += 1000000007
	print(tempanswer)


(n, k, d) = [int(x) for x in input().split()]
dp = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	dp[i] = sum([dp[i - j] for j in range(1, k + 1) if i - j >= 0])
dp_d1 = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	dp_d1[i] = sum([dp_d1[i - j] for j in range(1, min(k + 1, d)) if i - j >= 0])
print((dp[n] - dp_d1[n]) % (10 ** 9 + 7))


(desiredWeight, maxEdgeWeight, minEdgeWeight) = [int(x) for x in input().split()]
mic = [[0] * 5 for _ in range(desiredWeight + 1)]
modValue = 1000000007
mic[0][0] = 1
for i in range(1, desiredWeight + 1):
	for j in range(1, minEdgeWeight):
		if i - j < 0:
			break
		mic[i][0] += mic[i - j][0]
		mic[i][0] %= modValue
		mic[i][1] += mic[i - j][1]
		mic[i][1] %= modValue
	for j in range(minEdgeWeight, maxEdgeWeight + 1):
		if i - j < 0:
			break
		mic[i][1] += mic[i - j][0]
		mic[i][1] %= modValue
		mic[i][1] += mic[i - j][1]
		mic[i][1] %= modValue
print(mic[desiredWeight][1])


x = input()
x = x.split()
n = int(x[0])
k = int(x[1])
d = int(x[2])
limit = 1000000007
l0 = {0: 1}
ld = {0: 1}
for i in range(-k, 0):
	l0[i] = 0
for i in range(1, n + 1):
	l0[i] = 0
	for j in range(i - k, i):
		l0[i] += l0[j]
		if l0[i] > limit:
			l0[i] = l0[i] % limit
for i in range(d - k, d):
	if i != 0:
		ld[i] = 0
for i in range(d, n + 1):
	ld[i] = 0
	for j in range(i - k, i - d + 1):
		ld[i] += l0[j]
		if ld[i] > limit:
			ld[i] = ld[i] % limit
	for j in range(i - d + 1, i):
		ld[i] += ld[j]
		if ld[i] > limit:
			ld[i] = ld[i] % limit
print(ld[n])


mod = 1000000007
(n, k, d) = [int(i) for i in input().split()]
dp = [[0, 0] for i in range(n + 1)]
dp[0][1] = 0
dp[0][0] = 1
if n == 1:
	print(1 if d == 1 else 0)
else:
	for i in range(1, n + 1):
		total = 0
		for j in range(max(0, i - k), i):
			total += dp[j][0] % mod
		dp[i][0] = total % mod
	for i in range(1, n + 1):
		total = 0
		for j in range(max(0, i - d + 1), i):
			total += dp[j][1] % mod
		for j in range(max(0, i - k), max(0, i - d + 1)):
			total += dp[j][0] % mod
		dp[i][1] = total % mod
	print(int(dp[n][1] % mod))


def count(n, item):
	(new, x, summa, i) = ([], 1, 0, 0)
	for i in range(1, min(n + 1, item + 1)):
		new.append(x)
		summa += x
		x *= 2
		x = x % 1000000007
		summa = summa % 1000000007
	z = 0
	for j in range(i + 1, n + 1):
		new.append(summa)
		summa += new[-1] - new[z]
		summa = summa % 1000000007
		z += 1
	return new[-1]
(n, k, d) = map(int, input().split())
res = count(n, k) - count(n, d - 1)
if res < 0:
	res += 1000000007
print(res)


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
dp = []
d1 = n - d + 1
try:
	for i in range(d1 + 1):
		dp.append([])
		for j in range(n + 1):
			dp[i].append([0] * (d + 1))
	dp[0][0][0] = 1
	for i in range(0, d1):
		for j in range(i, n + 1):
			for y in range(d + 1):
				for x in range(1, min(n - j, k) + 1):
					dp[i + 1][j + x][min(max(x, y), d)] = (dp[i + 1][j + x][min(max(x, y), d)] + dp[i][j][y]) % mod
	ans = 0
	for i in range(d1 + 1):
		ans = (ans + dp[i][n][d]) % mod
	print(ans)
except:
	print(0)


(n, k, d) = map(int, input().split())
dp = [None, (0, 1)] if d > 1 else [None, (1, 1)]
for i in range(2, n + 1):
	if i < d:
		(s, u) = (0, 1)
	elif i <= k:
		s = u = 1
	else:
		s = u = 0
	for j in range(1, min(i, k + 1)):
		if j < d:
			s += dp[i - j][0]
		else:
			s += dp[i - j][1]
		u += dp[i - j][1]
	dp.append((s % 1000000007, u % 1000000007))
print(dp[-1][0])


def main():
	(n, k, d) = map(int, input().split())
	n += 1
	k += 1
	(l1le, l1ge) = ([0] * n, [0] * n)
	l1le[0] = 1
	res = 0
	for _ in range(n - d + 1):
		(l0le, l0ge, l1le, l1ge) = (l1le, l1ge, [0] * n, [0] * n)
		for (i, x) in enumerate(l0le):
			if x:
				x %= 1000000007
				for j in range(i + 1, i + d):
					if j < n:
						l1le[j] += x
				for j in range(i + d, i + k):
					if j < n:
						l1ge[j] += x
		for (i, x) in enumerate(l0ge):
			if x:
				x %= 1000000007
				for j in range(i + 1, i + k):
					if j < n:
						l1ge[j] += x
		res += l1ge[-1]
	print(res % 1000000007)
main()


MOD = 1000000007
(n, k, d) = map(int, input().split(' '))

def add(a, b):
	a += b
	return a % MOD
dp = [[0] * 2 for i in range(101)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j < 0:
			break
		if j < d:
			dp[i][0] = add(dp[i][0], dp[i - j][0])
			dp[i][1] = add(dp[i][1], dp[i - j][1])
		else:
			dp[i][1] = add(dp[i][1], dp[i - j][0])
			dp[i][1] = add(dp[i][1], dp[i - j][1])
print(dp[n][1])


import sys
input = sys.stdin.readline
(n, k, d) = map(int, input().split())
dp = [[0, 0] for i in range(n + 1)]
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	for j in range(1, min(i + 1, k + 1)):
		if j < d:
			dp[i][0] += dp[i - j][0]
		if j >= d:
			dp[i][1] += dp[i - j][0] + dp[i - j][1]
		else:
			dp[i][1] += dp[i - j][1]
		dp[i][0] %= mod
		dp[i][1] %= mod
print(dp[n][1])


(n, k, d) = map(int, input().split())
v = [1]
for i in range(1, n + 1):
	s = 0
	for j in range(max(0, i - k), i):
		s += v[j]
	v.append(s)
a = [1]
for i in range(1, n + 1):
	s = 0
	for j in range(max(0, i - d + 1), i):
		s += a[j]
	a.append(s)
print((v[len(v) - 1] - a[len(a) - 1]) % 1000000007)


t = 10 ** 9 + 7
(n, k, d) = map(int, input().split())
dp = [[0 for i in range(k + 1)] for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		if j < d:
			dp[i][0] = (dp[i][0] % t + dp[i - j][0] % t) % t
			dp[i][1] = (dp[i][1] % t + dp[i - j][1] % t) % t
		else:
			dp[i][1] = (dp[i][1] % t + dp[i - j][0] % t + dp[i - j][1] % t) % t
print(dp[n][1])


MOD = 10 ** 9 + 7
(n, k, d) = [int(k) for k in input().split()]
ways1 = [0] * (n + 1)
ways1[0] = 1
ways1[1] = 1
for i in range(2, n + 1):
	for j in range(max(0, i - k), i):
		ways1[i] += ways1[j]
	ways1[i] %= MOD
ways2 = [0] * (n + 1)
ways2[0] = 1
ways2[1] = 1
if d == 1:
	ways2[0] = 0
	ways2[1] = 0
for i in range(2, n + 1):
	for j in range(max(0, i - (d - 1)), i):
		ways2[i] += ways2[j]
	ways2[i] %= MOD
print((ways1[n] - ways2[n]) % MOD)


MOD = 1000000007
dp = [[-1 for i in range(2)] for j in range(101)]

def k_tree(n, k, d, least_d_selected):
	if least_d_selected:
		selected_index = 1
	else:
		selected_index = 0
	if n < 0:
		return 0
	if n == 0 and least_d_selected:
		return 1
	if n == 0 and (not least_d_selected):
		return 0
	temp = 0
	if dp[n][selected_index] != -1:
		return dp[n][selected_index]
	for i in range(k):
		if not least_d_selected and i + 1 >= d:
			temp += k_tree(n - (i + 1), k, d, True)
			temp %= MOD
		else:
			temp += k_tree(n - (i + 1), k, d, least_d_selected)
			temp %= MOD
	dp[n][selected_index] = temp
	return dp[n][selected_index]

def k_tree_runner():
	line = input()
	(sn, sk, sd) = line.split(' ')
	n = int(sn)
	k = int(sk)
	d = int(sd)
	print(k_tree(n, k, d, False))
k_tree_runner()


(n, k, d) = map(int, input().split())
b = 10 ** 9 + 7
ways = [0] * (n + 1)
ways.insert(0, 0)
j = 1
s = 0
while j <= min(k, n):
	ways[j] = 1
	j += 1
s += ways[n]
for i in range(2, n + 1):
	new_ways = [0] * (n + 1)
	for j in range(1, n + 1):
		for p in range(1, k + 1):
			if j + p <= n:
				new_ways[j + p] += ways[j]
	ways = []
	for j in new_ways:
		ways.append(j)
	s += ways[n]
	s = s % b
ways = [0] * (n + 1)
ways.insert(0, 0)
j = 1
r = 0
while j <= min(d - 1, n):
	ways[j] = 1
	j += 1
r += ways[n]
for i in range(2, n + 1):
	new_ways = [0] * (n + 1)
	for j in range(1, n + 1):
		for p in range(1, d):
			if j + p <= n:
				new_ways[j + p] += ways[j]
	ways = []
	for j in new_ways:
		ways.append(j)
	r += ways[n]
	r = r % b
print((s - r) % b)


ar = []
for i in input().split(' '):
	ar.append(int(i))
n = ar[0]
k = ar[1]
d = ar[2]
dict = {}
dict[0] = [1, 0]
for i in range(n + 1):
	for j in range(1, k + 1):
		if j >= d:
			if i + j in dict:
				dict[i + j][1] = dict[i][0] + dict[i][1] + dict[i + j][1]
			else:
				dict[i + j] = [0, dict[i][0] + dict[i][1]]
		elif i + j in dict:
			dict[i + j][0] = dict[i][0] + dict[i + j][0]
			dict[i + j][1] = dict[i][1] + dict[i + j][1]
		else:
			dict[i + j] = [dict[i][0], dict[i][1]]
print(dict[n][1] % 1000000007)


(n, x, d) = map(int, input().strip().split())
(dp, mod) = ([[0, 0] for _ in range(n + 1)], 10 ** 9 + 7)
(dp[0][0], dp[0][1]) = (1, 0)
for total in range(1, n + 1):
	for edge in range(1, x + 1):
		if total - edge < 0:
			break
		if edge < d:
			dp[total][0] = (dp[total][0] + dp[total - edge][0]) % mod
			dp[total][1] = (dp[total][1] + dp[total - edge][1]) % mod
		else:
			dp[total][1] = (dp[total][1] + dp[total - edge][0]) % mod
			dp[total][1] = (dp[total][1] + dp[total - edge][1]) % mod
print(dp[n][1])


dp = []

def f(n, k, d):
	global dp
	if n < 0:
		return 0
	if n == 0 and d == 0:
		dp[n][k][d] = 1
		return 1
	if dp[n][k][d] != -1:
		return dp[n][k][d]
	cont = 0
	for i in range(1, k + 1):
		cont += f(n - i, k, 0 if i >= d else d)
	dp[n][k][d] = cont
	return cont

def main():
	global dp
	(n, k, d) = [int(i) for i in input().split()]
	dp = [[[-1 for j2 in range(d + 1)] for j in range(k + 1)] for i in range(n + 1)]
	print(f(n, k, d) % 1000000007)
	return
main()


import sys
f = sys.stdin
(n, k, d) = map(int, f.readline().strip().split())
Nd = [[1] * (n + 1), [1] * (n + 1)]
Nd[1][0] = 0
Nd[1][1] = 0
for i in range(2, n + 1):
	N = 0
	for j in range(1, k + 1):
		if i >= j:
			N += Nd[0][i - j]
	Nd[0][i] = N
	N = 0
	for j in range(1, k + 1):
		if i >= j:
			if j >= d:
				N += Nd[0][i - j]
			else:
				N += Nd[1][i - j]
	Nd[1][i] = N
if d > 1:
	print(Nd[1][n] % 1000000007)
else:
	print(Nd[0][n] % 1000000007)


def main():
	mod = 10 ** 9 + 7
	(n, k, d) = map(int, input().split())
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j >= 0:
				dp[i] += dp[i - j]
			dp[i] %= mod
		if i <= k:
			dp[i] += 1
	dp1 = [0] * (n + 1)
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j >= 0 and j < d:
				dp1[i] += dp1[i - j]
			dp1[i] %= mod
		if i <= k and i < d:
			dp1[i] += 1
	ans = dp[n] - dp1[n]
	print(ans % mod)
main()


b = [False] * 101
x = [0] * 101

def count(w, k1):
	if w == 0:
		return 1
	elif w < 0:
		return 0
	ans = 0
	for i in range(1, k1 + 1):
		if w - i < 0:
			break
		if b[w - i]:
			ans = ans + x[w - i]
		else:
			x[w - i] = count(w - i, k1)
			ans = ans + x[w - i]
			b[w - i] = True
	b[w] = True
	x[w] = ans
	return ans
(n, k, d) = map(int, input().split())
x[0] = 1
ans = count(n, k)
b = [False] * 101
x = [0] * 101
x[0] = 1
ans = ans - count(n, min(k, d - 1))
print(ans % 1000000007)


I = lambda : list(map(int, input().split(' ')))

def path(total, num):
	if total in mem:
		return mem[total]
	if total == 0:
		return 1
	else:
		mem[total] = 0
		for i in range(1, num + 1):
			if total - i >= 0:
				mem[total] += path(total - i, num)
			else:
				break
		return mem[total]

def ans(n, k, d):
	global mem
	mem = {}
	a = path(n, k)
	if d > 1:
		mem = {}
		b = path(n, d - 1)
	else:
		b = 0
	return a - b
(n, k, d) = I()
print(ans(n, k, d) % int(10 ** 9 + 7))


MOD = 1000000007
(n, k, d) = map(int, input().split())
dp1 = [0] * (n + 5)
dp2 = [0] * (n + 5)
dp1[0] = 1
dp2[0] = 1
for i in range(1, n + 1):
	s = 0
	for j in range(1, k + 1):
		if j <= i:
			s = (s + dp1[i - j]) % MOD
	dp1[i] = s
for i in range(1, n + 1):
	s = 0
	for j in range(1, k + 1):
		if j <= i:
			if j >= d:
				s = (s + dp1[i - j]) % MOD
			elif i - j >= d:
				s = (s + dp2[i - j]) % MOD
	dp2[i] = s
print(dp2[n])


def calculateWays(summ, maxNumber):
	p = [0] * (summ + 1)
	dp = []
	for i in range(summ + 1):
		dp.append(p.copy())
	for i in range(summ):
		for j in range(summ):
			x = i + 1
			y = j + 1
			if x <= y:
				prevWays = 0
				for ii in range(y - 1):
					if ii < maxNumber:
						prevWays = (prevWays + dp[x - 1][y - ii - 1]) % 1000000007
				if y <= maxNumber and x == 1:
					dp[x][y] = (prevWays + 1) % 1000000007
				else:
					dp[x][y] = prevWays % 1000000007
	ans = 0
	for i in range(summ):
		ans = ans + dp[i + 1][summ]
	return ans

def main():
	(n, k, d) = list(map(int, input().split()))
	print((calculateWays(n, k) - calculateWays(n, d - 1)) % 1000000007)
main()


import sys
sys.setrecursionlimit(100000)
(n, k, d) = [int(x) for x in sys.stdin.readline().strip().split()]
memo = {}
m = 10 ** 9 + 7

def dp(n, k, d):
	key = str(n) + str(d)
	if n == 0:
		return 1
	if n < 0:
		return 0
	if key in memo:
		return memo[key]
	s = 0
	for i in range(1, k + 1):
		if i >= d:
			s += dp(n - i, k, 0)
		elif n - i >= d:
			s += dp(n - i, k, d)
	memo[key] = s
	return s
print(dp(n, k, d) % m)


(n, k, d) = map(int, input().split())
dp = [0] * (n + 1)
mod = 10 ** 9 + 7
dp[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i >= j:
			dp[i] += dp[i - j]
	dp[i] %= mod
if d == 1:
	print(dp[n])
else:
	dp1 = [0] * (n + 1)
	dp1[0] = 1
	for i in range(1, n + 1):
		for j in range(1, d):
			if i >= j:
				dp1[i] += dp1[i - j]
		dp1[i] %= mod
	print((dp[n] - dp1[n]) % mod)


(n, k, d) = list(map(int, input('').split()))
arr = [0] * (n + 1)
arr[0] = (0, 1)
num_list = [i for i in range(1, k + 1)]
for i in range(1, n + 1):
	if i < d:
		total_paths = 0
		for num in num_list:
			if i - num >= 0:
				total_paths += arr[i - num][1]
		arr[i] = (0, total_paths)
	else:
		all_paths = 0
		conditioned_paths = 0
		for num in num_list:
			if num >= d and i - num >= 0:
				all_paths += arr[i - num][1]
				conditioned_paths += arr[i - num][1]
			elif i - num >= 0:
				all_paths += arr[i - num][1]
				conditioned_paths += arr[i - num][0]
		arr[i] = (conditioned_paths, all_paths)
print(arr[n][0] % 1000000007)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, k, d) = LI()
	fm = {}

	def f(n, df):
		key = (n, df)
		if key in fm:
			return fm[key]
		if not df and n < d or n < 0:
			fm[key] = 0
			return 0
		if n == 0:
			fm[key] = 1
			return 1
		r = 0
		for i in range(1, k + 1):
			r += f(n - i, df or i >= d)
		fm[key] = r % mod
		return fm[key]
	r = f(n, False)
	return r % mod
print(main())


MOD = 1000000007
line = input().split()
n = int(line[0])
k = int(line[1])
d = int(line[2])
dp = [[-1, -1] for i in range(100000)]

def rec(num, gud):
	global k, d
	if num < 0:
		return 0
	if num == 0:
		return gud
	if dp[num][gud] != -1:
		return dp[num][gud]
	dp[num][gud] = 0
	for i in range(1, k + 1):
		dp[num][gud] += rec(num - i, gud or i >= d) % MOD
	dp[num][gud] = dp[num][gud] % MOD
	return dp[num][gud]
print(rec(n, 0))


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, min(n, k) + 1):
	dp[1][i] = 1
for i in range(2, n + 1):
	for j in range(1, n + 1):
		for l in range(1, min(j, k) + 1):
			dp[i][j] += dp[i - 1][j - l]
			dp[i][j] %= mod
dp2 = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, min([d - 1, k, n]) + 1):
	dp2[1][i] = 1
for i in range(2, n + 1):
	for j in range(1, n + 1):
		for l in range(1, min([j, k, d - 1]) + 1):
			dp2[i][j] += dp2[i - 1][j - l]
			dp2[i][j] %= mod
ans = 0
for i in range(1, n + 1):
	ans += dp[i][n] - dp2[i][n]
	ans %= mod
print(ans)


mod = int(1000000000.0 + 7)
(n, k, d) = map(int, input().split())
dp = [[-1 for _ in ' ' * 2] for _ in range(101)]

def ktree(sum, ch):
	if sum > n:
		return 0
	if sum == n:
		if ch:
			return 1
		else:
			return 0
	if dp[sum][ch] != -1:
		return dp[sum][ch]
	ans = 0
	for i in range(1, k + 1):
		if i < d:
			ans += ktree(sum + i, ch) % mod
		else:
			ans += ktree(sum + i, 1)
	dp[sum][ch] = ans % mod
	return ans % mod
print(ktree(0, 0))


def count(b, n):
	a = [0] * (n + 1)
	m = len(b)
	a[0] = 1
	for i in range(1, n + 1):
		for j in range(m):
			if i >= b[j]:
				a[i] += a[i - b[j]]
	return a[n]
(n, k, d) = list(map(int, input().split()))
a = [i for i in range(1, k + 1)]
b = [i for i in range(1, d)]
print((count(a, n) - count(b, n)) % (10 ** 9 + 7))


import sys
sys.setrecursionlimit(100000)
dp = {}
mod = 1000000007

def F(N, k, d, x):
	global dp, mod
	if (N, x) in dp:
		return dp[N, x]
	if N == 0:
		if x == 1:
			return 1
		else:
			return 0
	if N < 0:
		return 0
	S = 0
	x1 = 0
	for i in range(1, k + 1):
		if x or i >= d:
			x1 = 1
		else:
			x1 = 0
		S = (S + F(N - i, k, d, x1) % mod) % mod
	dp[N, x] = S
	return S
(N, k, d) = map(int, input().strip().split())
L = F(N, k, d, 0)
print(L)


from sys import stdin
import math
__author__ = 'artyom'

def read_int_ary():
	return map(int, stdin.readline().strip().split())
(n, k, d) = read_int_ary()
cache = {0: {}, 1: {}}

def f(a, has_d):
	calced = cache[has_d].get(a)
	if calced:
		return calced
	if a < d and (not has_d):
		return 0
	if a <= 1 or (a <= d and (not has_d)):
		return 1
	sum = 0
	x = 1
	while x <= k and a - x >= 0:
		sum += f(a - x, has_d or x >= d)
		x += 1
	cache[has_d][a] = sum
	return sum
print(f(n, 0) % 1000000007) if n >= d else print(0)


def sol(n, k, d):
	if n <= d:
		if n == d:
			return 1
		else:
			return 0
	if (n, k, d) not in dic:
		ans = 0
		for i in range(1, k + 1):
			if i >= d:
				ans += sol(n - i, k, 0)
			else:
				ans += sol(n - i, k, d)
		dic[n, k, d] = ans % 1000000007
	return dic[n, k, d]
A = list(map(int, input().split()))
dic = {}
print(sol(A[0], A[1], A[2]))


import sys
c_mod = 1000000007
(n, k, d) = map(int, sys.stdin.readline().split())
dp = [0] * (n + 1)
dp_no = [0] * (n + 1)
dp[0] = 1
dp_no[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j <= i:
			dp[i] += dp[i - j]
			dp[i] %= c_mod
	for j in range(1, d):
		if j <= i:
			dp_no[i] += dp_no[i - j]
			dp_no[i] %= c_mod
print((dp[n] - dp_no[n] + c_mod) % c_mod)


from sys import stdin, stdout
from collections import defaultdict, Counter
from functools import lru_cache
from math import gcd, floor, ceil

def ilist():
	return [int(x) for x in stdin.readline().strip().split(' ')]

def iint():
	return int(stdin.readline().strip())

def istr():
	return stdin.readline().strip()

def solve(n, k):
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i - j >= 0:
				dp[i] += dp[i - j]
	return dp[n]
(n, k, d) = ilist()
print((solve(n, k) - solve(n, d - 1)) % 1000000007)


def F(n, k):
	if k < 2:
		return k
	b = [0] * (k - 1) + [1]
	for i in range(n):
		b.append(sum(b[-k:]) % (10 ** 9 + 7))
	return b[-1]
(n, k, d) = list(map(int, input().split()))
ans = F(n, k) - F(n, d - 1)
if ans < 0:
	ans += 10 ** 9 + 7
print(ans)


def main():
	from sys import stdin, stdout
	MOD = int(1000000000.0) + 7
	(n, k, d) = map(int, stdin.readline().split())
	d -= 1
	klist = [(1 << i) % MOD for i in range(k)]
	klist = [1] + klist
	for i in range(k + 1, n + 1):
		klist.append((klist[i - 1] * 2 - klist[i - 1 - k]) % MOD)
	if d:
		dlist = [(1 << i) % MOD for i in range(d)]
		dlist = [1] + dlist
		for i in range(d + 1, n + 1):
			dlist.append((dlist[i - 1] * 2 - dlist[i - 1 - d]) % MOD)
		ans = klist[n] - dlist[n]
	else:
		ans = klist[n]
	stdout.write(str(ans % MOD))
main()


from sys import stdin, stderr

def readInts():
	return map(int, stdin.readline().strip().split())

def print_err(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def naive_kt(k, d, n):
	if n < 0:
		return 0
	if n < d:
		return 0
	if n == 0:
		return 1
	s = 0
	for i in range(1, k + 1):
		d2 = 0
		if i >= d:
			d2 = 0
		else:
			d2 = d
		s += naive_kt(k, d2, n - i)
	return s

def dp_kt(k, d, n):
	a_d_used = [1]
	a_d_unused = [0]
	for ni in range(1, n + 1):
		s = 0
		for si in range(max(0, ni - k), ni):
			s += a_d_used[si]
		a_d_used.append(s)
	for ni in range(1, n + 1):
		s = 0
		for si in range(1, k + 1):
			if ni - si < 0:
				continue
			v = a_d_unused[ni - si]
			if si >= d:
				v = a_d_used[ni - si]
			s += v
		a_d_unused.append(s)
	return (a_d_used, a_d_unused)

def solve(vs):
	return None

def run():
	modval = 10 ** 9 + 7
	(n, k, d) = readInts()
	(_, dp) = dp_kt(k, d, n)
	print(dp[-1] % modval)
run()


import sys
input = sys.stdin.buffer.readline

def I():
	return list(map(int, input().split()))

def sieve(n):
	a = [1] * n
	for i in range(2, n):
		if a[i]:
			for j in range(i * i, n, i):
				a[j] = 0
	return a
MOD = 10 ** 9 + 7

def rec(s, f):
	if s < 0:
		return 0
	if s == 0:
		if f == 1:
			return 0
		else:
			return 1
	ans = 0
	if dp[s][f] != -1:
		return dp[s][f]
	for i in range(1, k + 1):
		if i < d:
			ans += rec(s - i, f)
		else:
			ans += rec(s - i, 0)
		ans %= MOD
	dp[s][f] = ans
	return ans
(n, k, d) = I()
dp = [[-1, -1] for i in range(n + 1)]
for i in range(n + 1):
	rec(i, 0)
	rec(i, 1)
print(rec(n, 1))


mod = 1000000007
(n, k, d) = map(int, input().split())
if n < d:
	print(0)
else:
	dp = [0] * (n + 1)
	dp[0] = 1
	dpp = [0] * (n + 1)
	dpp[0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if i >= j:
				dp[i] = (dp[i - j] + dp[i]) % mod
			if i >= j and j < d:
				dpp[i] = (dpp[i - j] + dpp[i]) % mod
	print((dp[n] - dpp[n]) % mod)


def f(k, n, d, b, l):
	if n < 0 or (b == 0 and n < d):
		return 0
	elif l[n][b] > 0:
		return l[n][b]
	else:
		cnt = 0
		for i in range(1, k + 1):
			if i < d:
				cnt += f(k, n - i, d, b, l)
			else:
				cnt += f(k, n - i, d, 1, l)
		l[n][b] = cnt
		return cnt
(n, k, d) = map(int, input().split())
l = [[0, 0] for i in range(n + 1)]
l[0] = [1, 1]
print(f(k, n, d, 0, l) % 1000000007)


(n, k, d) = map(int, input().split())
dp = [[0 for i in range(2)] for i in range(101)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(1, 101):
	dp[i][0] = sum((dp[j][0] for j in range(i - min(i, d), i)))
	if min(i, d) == d:
		dp[i][0] = dp[i][0] - dp[i - d][0]
	dp[i][1] = sum((dp[j][1] for j in range(i - min(i, k), i)))
pri = 10 ** 9 + 7
print((dp[n][1] - dp[n][0]) % pri)


import sys
from math import log2, floor, ceil, sqrt, gcd
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000007
(n, k, d) = Ri()
no = [0] * (n + 1)
no[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j > i:
			break
		no[i] += no[i - j]
nod = [0] * (n + 1)
nod[0] = 1
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j > i:
			break
		if j >= d:
			break
		nod[i] += nod[i - j]
print((no[n] - nod[n]) % MOD)


from collections import defaultdict

def add_mod(a, b):
	a += b
	if a >= mod:
		a -= mod
	return a
line = list(map(int, input().split()))
n = line[0]
k = line[1]
d = line[2]
dp = defaultdict(lambda : defaultdict(int))
dp[0][0] = 1
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	for j in range(1, min(i, k) + 1):
		if j < d:
			dp[i][0] = add_mod(dp[i][0], dp[i - j][0])
		else:
			dp[i][1] = add_mod(dp[i][1], dp[i - j][0])
		dp[i][1] = add_mod(dp[i][1], dp[i - j][1])
print(dp[n][1])


(n, k, d) = map(int, input().split())
(memoized_f, memoized_g) = ([-1] * (n + 1), [-1] * (n + 1))

def g(n, k):
	if memoized_g[n] == -1:
		memoized_g[n] = 0
		for i in range(1, k + 1):
			if i > n:
				break
			if i == n:
				memoized_g[n] += 1
			else:
				memoized_g[n] += g(n - i, k)
			memoized_g[n] %= 1000000007
	return memoized_g[n]

def f(n, k, d):
	if memoized_f[n] == -1:
		memoized_f[n] = 0
		for i in range(1, k + 1):
			if i > n:
				break
			if i == n:
				memoized_f[n] += i >= d
			else:
				memoized_f[n] += g(n - i, k) if i >= d else f(n - i, k, d)
			memoized_f[n] %= 1000000007
	return memoized_f[n]
print(f(n, k, d))


from sys import stdin

def calculate_main(n, k, mod):
	dp = [0] * (n + 1)
	dp[0] = 1
	dp[1] = 1
	for i in range(2, n + 1):
		for j in range(i - 1, max(-1, i - k - 1), -1):
			dp[i] += dp[j]
			dp[i] %= mod
	return dp
(n, k, d) = list(map(int, stdin.readline().split()))
mod = 10 ** 9 + 7
dp = calculate_main(n, k, mod)
dp2 = [0] * (n + 1)
for i in range(d, n + 1):
	for j in range(1, min(k + 1, i + 1)):
		if j < d:
			dp2[i] += dp2[i - j]
			dp2[i] %= mod
		else:
			dp2[i] += dp[i - j]
			dp2[i] %= mod
print(dp2[n] % mod)


mod = 10 ** 9 + 7
(n, k, d) = map(int, input().strip().split())
notD = [0 for i in range(n + 1)]
notD[0] = 1
withD = [0 for i in range(n + 1)]
withD[0] = 1
for i in range(n + 1):
	for j in range(1, d):
		if i >= j:
			notD[i] += notD[i - j]
for i in range(n + 1):
	for j in range(1, k + 1):
		if i >= j:
			withD[i] += withD[i - j]
print((withD[n] - notD[n]) % mod)


(n, k, d) = map(int, input().split())
mod = 10 ** 9 + 7
memo = {}

def DFS(hasD=False, totalSum=n):
	global memo
	c = 0
	startD = hasD
	for i in range(1, k + 1):
		hasD = startD
		if i >= d:
			hasD = True
		if totalSum - i == 0:
			if hasD:
				c += 1
			break
		if (hasD, totalSum - i) not in memo:
			memo[hasD, totalSum - i] = DFS(hasD, totalSum - i)
		c += memo[hasD, totalSum - i]
	return c % mod
print(DFS())


def run():
	(n, k, d) = (int(x) for x in input().split(' '))
	value = recurse(n, k, d, 0, dict()) % 1000000007
	print(value)

def recurse(n, k, d, r, memo):
	if n == 0:
		if d == -1:
			return 1
		else:
			return 0
	elif n < 0:
		return 0
	key = 'level={}, n={}, d={}'.format(r, n, d)
	if key in memo.keys():
		return memo[key]
	total = 0
	for p in range(1, min(n + 1, k + 1)):
		if p >= d:
			d = -1
		value = recurse(n - p, k, d, r + 1, memo)
		total += value
	memo[key] = total
	return total
run()


(N, K, D) = map(int, input().split())
mod = 10 ** 9 + 7
dpK = [0 for i in range(N + 1)]
dpK[0] = 1
for i in range(1, N + 1):
	for j in range(1, K + 1):
		if i >= j:
			dpK[i] += dpK[i - j]
	dpK[i] %= mod
dp = [0 for i in range(N + 1)]
dp[0] = 1
for i in range(1, N + 1):
	for j in range(1, D):
		if i >= j:
			dp[i] += dp[i - j]
	dp[i] %= mod
ans = dpK[N] - dp[N]
print(ans % mod)


(n, k, d) = map(int, input().split())
done = {}

def num_pos(i, d_in):
	if (i, d_in) in done:
		return done[i, d_in]
	if i == 0 and d_in:
		return 1
	if i == 0:
		return 0
	pos = 0
	for v in range(1, k + 1):
		if v > i:
			break
		pos += num_pos(i - v, d_in or v >= d)
	done[i, d_in] = pos
	return pos
print(num_pos(n, False) % 1000000007)


(n, k, d) = [int(x) for x in input().split()]
mod = 10 ** 9 + 7
dp = [[0 for x in range(2)] for y in range(107)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i - j >= 0:
			if j < d:
				dp[i][0] = (dp[i][0] % mod + dp[i - j][0] % mod) % mod
			else:
				dp[i][1] = (dp[i][1] % mod + dp[i - j][0] % mod) % mod
			dp[i][1] = (dp[i][1] % mod + dp[i - j][1] % mod) % mod
print(dp[n][1] % mod)


from functools import lru_cache

@lru_cache(10000000)
def fsum(n, k):
	if k > n:
		k = n
	if n == 0:
		return 1
	paths = 0
	for i in range(1, k + 1):
		paths += fsum(n - i, k)
	return paths
(n, k, d) = map(int, input().split(' '))
a = fsum(n, k)
b = fsum(n, d - 1)
print((fsum(n, k) - fsum(n, d - 1)) % 1000000007)


(n, k, d) = input().split()
n = int(n)
k = int(k)
d = int(d)
dp = [[0 for i in range(n + 1)] for j in range(k + 1)]
for i in range(k + 1):
	dp[i][0] = 1
for j in range(1, n + 1):
	for i in range(1, k + 1):
		dp[i][j] = sum(dp[i][max(0, j - i):j + 1])
print((dp[k][n] - dp[d - 1][n]) % (10 ** 9 + 7))


(n, k, d) = [int(x) for x in input().split(' ')]
MOD = 1000000000.0 + 7
ps = {}
ps2 = {}

def dfs(n_left):
	count = 0
	for i in range(1, k + 1):
		if n_left - i == 0:
			count += 1
			break
		if n_left - i in ps:
			inner_count = ps[n_left - i]
		else:
			inner_count = dfs(n_left - i)
		count += inner_count % MOD
	ps[n_left] = count % MOD
	return ps[n_left]

def dfs2(n_left):
	count = 0
	for i in range(1, d):
		if n_left - i == 0:
			count += 1
			break
		if n_left - i in ps2:
			inner_count = ps2[n_left - i]
		else:
			inner_count = dfs2(n_left - i)
		count += inner_count % MOD
	ps2[n_left] = count % MOD
	return ps2[n_left]
ans = dfs(n) - dfs2(n) + MOD
print(int(ans % MOD))


(n, k, d) = map(int, input().split())
meme = [[-1 for i in range(2)] for j in range(123)]

def fucc(qtd, zeroum):
	global meme
	global n
	global k
	global d
	if zeroum == 1 and qtd == n:
		return 1
	if qtd >= n:
		return 0
	if meme[qtd][zeroum] != -1:
		return meme[qtd][zeroum]
	tmp = zeroum
	res = 0
	for i in range(1, k + 1):
		if i >= d:
			tmp = 1
		res += fucc(qtd + i, tmp) % 1000000007
	meme[qtd][zeroum] = res
	return res
print(fucc(0, 0) % 1000000007)


def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	(n, k, d) = read_ints()
	modulo = 10 ** 9 + 7
	OPT = [[0, 0] for _ in range(n + 1)]
	OPT[0][False] = 1
	for i in range(1, n + 1):
		OPT[i][False] = sum((OPT[i - j][False] for j in range(1, min(i + 1, d)))) % modulo
		OPT[i][True] = (sum((OPT[i - j][False] for j in range(d, min(i + 1, k + 1)))) + sum((OPT[i - j][True] for j in range(1, min(i + 1, k + 1))))) % modulo
	return OPT[-1][True]
print(solve())


mod = int(1000000000.0 + 7)
(n, k, d) = map(int, input().split())
dp = [[0 for _ in ' ' * 2] for _ in range(n + 1)]
dp[0][0] = 1
dp[0][1] = 0
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if i < j:
			break
		dp[i][j >= d] += dp[i - j][0] % mod
		dp[i][1] += dp[i - j][1] % mod
print(dp[n][1] % mod)


def func(n, k):
	arr = [0 for i in range(n + 1)]
	arr[0] = 1
	if n <= 0:
		return 0
	for j in range(1, n + 1):
		for i in range(1, min(k + 1, j + 1)):
			arr[j] += arr[j - i]
	return arr[n]
(n, k, d) = map(int, input().split())
p = 1000000007
print((func(n, k) - func(n, d - 1)) % p)


mod = 1000000007

def sol(n, k):
	arr = [0 for i in range(n + 1)]
	acum = [0 for i in range(n + 1)]
	for i in range(1, min(k, n) + 1):
		arr[i] = 1
		acum[i] = 1
	for qq in range(n):
		arr1 = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, k + 1):
				if arr[i] != 0 and i + j < len(arr1):
					arr1[i + j] = (arr1[i + j] + arr[i]) % mod
		for i in range(n + 1):
			acum[i] = (acum[i] + arr1[i]) % mod
		arr = arr1.copy()
	return acum[-1]
from sys import stdin
(n, k, d) = map(int, stdin.readline().strip().split())
print((sol(n, k) - sol(n, d - 1)) % mod)


import sys
import math
import operator as op
from functools import reduce

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom
N = int(1000000.0) + 10
fenwick = [0] * N

def add(i, x, n):
	while i < n:
		fenwick[i] += x
		i = i | i + 1

def fsum(i, n):
	res = 0
	while i >= 0:
		res += fenwick[i]
		i = (i & i + 1) - 1
	return res

def fsum_range(i, j, n):
	return fsum(j, n) - fsum(i - 1, n)
mod = int(1000000000.0) + 7
t = 1
for i in range(t):
	(n, k, d) = read_int_line()
	dp = [[0, 0] for i in range(n + 1)]
	dp[0][0] = 1
	dp[0][1] = 0
	for i in range(1, n + 1):
		for j in range(1, min(d - 1, i) + 1):
			dp[i][0] += dp[i - j][0]
		for j in range(1, min(d - 1, i) + 1):
			dp[i][1] += dp[i - j][1]
		for j in range(d, min(k, i) + 1):
			dp[i][1] += dp[i - j][0] + dp[i - j][1]
	print(dp[n][1] % mod)


m = 1000000007

def mod_add(a, b):
	return (a % m + b % m) % m

def solve(n, k, d, flag, dp):
	if n < 0:
		return 0
	if n == 0:
		if flag == False:
			return 1
		else:
			return 0
	if (n, flag) in dp:
		return dp[n, flag]
	temp = 0
	f = flag
	for i in range(1, k + 1):
		if i >= d:
			flag = False
		temp = mod_add(temp, solve(n - i, k, d, flag, dp))
	dp[n, f] = temp
	return temp
arr = [int(x) for x in input().split()]
print(solve(arr[0], arr[1], arr[2], True, {}))


a = input()
list_a = list(map(int, a.split()))
n = list_a[0]
k = list_a[1]
d = list_a[2]
solutions = []
for numbers in range(n + 1):
	solutions.append(-1)

def dp(n, k, solutions):
	if n == 1:
		solutions[1] = 1
		return 1
	if solutions[n] != -1:
		return solutions[n]
	else:
		answer = 0
		x = 1
		while n - x > 0 and x <= k:
			answer += dp(n - x, k, solutions)
			x += 1
		if n <= k:
			answer += 1
		solutions[n] = answer
		return answer
solutions_copy = []
for numbers in range(n + 1):
	solutions_copy.append(-1)

def dp_2(n, k, solutions_copy, d):
	if n == 1:
		solutions_copy[1] = 1
		return 1
	if solutions_copy[n] != -1:
		return solutions_copy[n]
	else:
		answer = 0
		x = 1
		while n - x > 0 and x <= k:
			if x < d:
				answer += dp_2(n - x, k, solutions_copy, d)
				x += 1
			else:
				x += 1
				continue
		if n <= k and n < d:
			answer += 1
		solutions_copy[n] = answer
		return answer
if n == d == 1:
	print(1)
else:
	print((dp(n, k, solutions) - dp_2(n, k, solutions_copy, d)) % (10 ** 9 + 7))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log, pi, sin
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

@lru_cache(None)
def recur(number, flag=False):
	if number > n:
		return 0
	if number == n:
		return int(flag)
	answer = 0
	for temp in arr:
		answer += recur(number + temp, flag or temp >= d)
		if answer > mod:
			answer -= mod
	return answer % mod
(n, k, d) = sp()
arr = []
for i in range(1, k + 1):
	arr.append(i)
out(recur(0))


(n, k, d) = map(int, input().split())
s1 = [0] * 110
s2 = [0] * 110
(s1[0], s2[0]) = (1, 1)
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	for j in range(1, k + 1):
		if j > i:
			break
		else:
			s1[i] += s1[i - j]
	for j in range(1, d):
		if j > i:
			break
		else:
			s2[i] += s2[i - j]
print((s1[n] - s2[n]) % mod)


inp = input().split()
n = int(inp[0])
k = int(inp[1])
d = int(inp[2])
dp = []
for i in range(0, 110):
	dp.append(0)
dp[0] = 1
for i in range(0, n):
	for j in range(1, k + 1):
		if i + j > n:
			break
		else:
			dp[i + j] = dp[i + j] + dp[i]
dp2 = []
for i in range(0, 110):
	dp2.append(0)
dp2[0] = 1
for i in range(0, n):
	for j in range(1, d):
		if i + j > n:
			break
		else:
			dp2[i + j] = dp2[i + j] + dp2[i]
print((dp[n] - dp2[n]) % 1000000007)


(n, k, d) = map(int, input().split())
dp = [[0 for j in range(2)] for i in range(105)]
dp[0][1] = 1
for i in range(1, n + 1):
	for j in range(1, min(i, k) + 1):
		dp[i][0] = (dp[i][0] + dp[i - j][j >= d]) % 1000000007
		dp[i][1] = (dp[i][1] + dp[i - j][1]) % 1000000007
print(dp[n][0])