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

最近，一个富有创造力的学生 Lesha 听了关于树的讲座。讲座结束后，Lesha 备受启发，创造了一棵自己的树，他称之为 k-树。

k-树 是一棵无限的有根树，其中：

1. 每个顶点恰好有 $k$ 个子节点；
2. 每条边都有一定的权重；
3. 如果我们查看从某个顶点到其子节点的边 (恰好 $k$ 条边)，则它们的权重将等于 $1,2,3,…,k$。

下图展示了一棵 3-树 的一部分。

Lesha 的好朋友 Dima 发现了这棵树，他想：“从一棵 k-树 的根节点开始，且至少包含一条权重不小于 $d$ 的边，这样的总权重等于 $n$ 的路径有多少条呢？” 路径的总权重等于该路径各边权重之和。

请帮助 Dima 找到问题的答案。由于路径数量可能相当多，所以请将答案对 $10^9+7$ 取模后输出。

输入

$T(T≤ 10)$ 组测试数据，每组数据格式如下：

输入三个整数 $n,k,d(1≤n,k≤100,1≤d≤k)$。

输出

每组数据输出一行，包含一个整数。

3 3 2
3 3 3
4 3 2
4 5 2

3
1
6
7

k-Tree CodeForces - 431C