题目描述

定义 k-tree 是一个有根树，并且满足：

• 每一个非叶子节点都有 $k$ 个孩子节点；
• 每一条边都有一个边权；
• 每一个非叶子节点指向其 $k$ 个孩子节点的 $k$ 条边的权值分别为 $1,2,3,⋯,k$。

求有多少条从 k-tree 的根节点出发的路径满足它们的边权之和等于 $n$，并且经过的这些边中至少有一条边的边权大于等于 $d$。答案对 $10^9+7$ 取模。

输入格式

一行三个整数 $n,k,d$，$1\le n,k\le 100$，$1\le d\le k$。

输出格式

一个整数表示答案，对 $10^9+7$ 取模。

3 3 2

3

3 3 3

1

4 3 2

6

4 5 2

7