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.

 

 <img class="tex-graphics" src="https://espresso.codeforces.com/61ac5ac17c4d2f220968eff8fb59bb3c8dc77edf.png" style="max-width: 100.0%;max-height: 100.0%;"/>

 

Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
A single line contains three space-separated integers: *n*, *k* and *d* (1 ≤ *n*, *k* ≤ 100; 1 ≤ *d* ≤ *k*).
import sys

class Solution():
    def __init__(self, n: int, k: int, d: int):
        self.dp = [[-1 for _ in range(2)] for _ in range(n + 1)]
        self.k = k
        self.d = d

    def solve(self, n: int, found: bool):
        if self.dp[n][found] != -1:
            return self.dp[n][found]
        
        if n == 0:
            if found:
                self.dp[n][found] = 1
                return self.dp[n][found]
            else:
                self.dp[n][found] = 0
                return self.dp[n][found]

        ans = 0
        if found:
            for i in range(1, self.k + 1):
                if n - i >= 0:
                    ans += self.solve(n - i, True)
        else:
            for i in range(1, self.k + 1):
                if n - i >= 0:
                    if i < self.d:
                        ans += self.solve(n - i, False)
                    else:
                        ans += self.solve(n - i, True)

        self.dp[n][found] = ans
        return self.dp[n][found]

def main():
    n, k, d = (int(x) for x in sys.stdin.readline().split())
    
    obj = Solution(n, k, d)
    print(obj.solve(n, False))

    return
    



if __name__ == "__main__":
    main()