431C.md (1556B)
1 Source: https://codeforces.com/problemset/problem/431/C 2 3 C. k-Tree 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 A *k*-tree is an infinite rooted tree where: 24 25 * each vertex has exactly *k* children; 26 * each edge has some weight; 27 * 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*. 28 29 The picture below shows a part of a 3-tree. 30 31  32 33 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*?". 34 35 Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7). 36 37 Input 38 39 A single line contains three space-separated integers: *n*, *k* and *d* (1 ≤ *n*, *k* ≤ 100; 1 ≤ *d* ≤ *k*). 40 41 Output 42 43 Print a single integer — the answer to the problem modulo 1000000007 (109 + 7). 44 45 Examples 46 47 Input 48 49 ``` 50 3 3 2 51 ``` 52 53 Output 54 55 ``` 56 3 57 ``` 58 59 Input 60 61 ``` 62 3 3 3 63 ``` 64 65 Output 66 67 ``` 68 1 69 ``` 70 71 Input 72 73 ``` 74 4 3 2 75 ``` 76 77 Output 78 79 ``` 80 6 81 ``` 82 83 Input 84 85 ``` 86 4 5 2 87 ``` 88 89 Output 90 91 ``` 92 7 93 ```