该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一个无限大的树，从根节点开始，每个节点都有 $k$ 个孩子，对应边权分别为 $1$ 到 $k$ 。

问从根开始，有多少条路径满足以下条件：

$1$ . 路径中至少包括一条权重大于等于 $d$ 的边。

$2$ . 路径的边权总和为 $n$ 。

由于答案可能很大，输出对 $1e9+7$ 取模的结果。

输入格式

第一行：包含三个整数： $n,k,d$ （ $1 \le  n, k \le  100; 1 \le  d \le  k$ ） 中间用空格分隔。

输出格式

输出方案数模 $1e9+7$

数据范围

对于 $100\%$ 的数据， $1 \le n,k \le 100, 1 \le d \le k$ 。

输入样例 1

3 3 2

输出样例 1

3