题目描述

你的音乐播放器里有 n 首不同的歌，在旅途中，你计划听 goal 首歌（不一定不同，即，允许歌曲重复）。你将会按如下规则创建播放列表：

• 每首歌 至少播放一次 。
• 一首歌只有在其他 k 首歌播放完之后才能再次播放。

给你 n、goal 和 k ，返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回对 $10^9 + 7$ 取余 的结果。

输入格式

一行空格隔开的三个整数分别表示 $n$， $goal$， $k$。

输出格式

一行一个整数表示答案。

示例 1：

3 3 1

6

解释: 有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1] 。

示例 2：

2 3 0

6

解释: 有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2] 。

示例 3：

2 3 1

2

解释: 有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2] 。

提示：

• $0 <= k < n <= goal <= 100$

SOURCE

播放列表的数量