Description

ZSL 要外出旅游，他的旅途一共有$n$天，他带上了$m$件衣服。每天他都会穿一件衣服，但是他不想在连续的$p$天内穿同一件衣服两次以上，他想知道在他$n$天的旅行中有多少种穿法，由于数字可能很大，你需要对其模上$1\ 000\ 000\ 007$。

Input Format

输入文件名为travel.in。

输入数据仅一行，包含三个正整数$m$，$n$，$p$，他们之间用一个空格隔开，意义见题目描述。

Output Format

输出文件名为travel.out。

输出仅一行，一个自然数，意义见题目描述。

Sample

样例输入 1

3 4 3

样例输出 1

6

样例解释 1

满足条件的穿法有$(1,2,3,1)$，$(1,3,2,1)$，$(2,1,3,2)$，$(2,3,1,2)$，$(3,1,2,3)$，$(3,2,1,3)$共$6$种。

Hint

对于$10\%$的数据：$m,n\le 8$。
对于$50\%$的数据：$n\le 100$，$m\le 1\ 000$。
另有$10\%$的数据：$n\le 5\ 000$，$p\le 2$。
另有$10\%$的数据：$n\le 1\ 000$，$m,p\le 7$。
对于$80\%$的数据：$n\le 2\ 000$。
对于$100\%$的数据：$n\le 5\ 000$，$m\le 1\ 000\ 000\ 000$，$p\le m,n$。