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

【题目描述】

有 n 个小球，编号为 1 ~ n。

有 m 个盒子，编号为 1 ~ m。

Bob 要将这 n 个小球装进 m 个盒子。他要求：

1.每个盒子中至少有一个小球。

2.如果一个盒子中有不止一个小球，则该盒子中任意两个小球的编号的差的绝对值都不能小于 k。

问：Bob 有多少种不同的装球方案？

两种方案被认为不同，当且仅当存在一个小球 i, 在两种方案中放入的盒子的编号不同。

输出方案数模 1,000,000,007 的值。

【输入格式】

一行三个整数：n、m、k。

【输出格式】

一个整数：方案数模 1,000,000,007 的值。

【样例1输入】

3 2 2

【样例1输出】

2

【样例1解释】

用 1, 2, 3 表示三个小球，A, B 表示两个盒子，则会有以下 2 种可能（同一括号内表示同一个盒子内的小球）：

A(1, 3), B(2)

A(2), B(1, 3)

【样例2输入】

987 654 321

【样例2输出】

23672795

【数据规模与约定】