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

绘画天赋

p5.cpp 1000ms, 512MB

【题目描述】

小Q很喜欢画画，他自认为天赋颇高，但实际上又菜又爱玩。即便如此，他还是坚持不懈地创作抽象派画作。 今天小Q灵感突发，想要画直线。他准备画一条长度恰好为n个像素的线段。他的画笔共有k种颜色，每个像素格上都需要画上一种颜色，线段上这些颜色可以随意组合。他认为一条符合要求的线段中，最长的由同一颜色的像素构成的连续子段需要有不少于c的长度。 例如：n=5,k=2,c=3时，”22111”是一条合法的线段， “21221”不是一条合法的线段。 小Q认为这些色彩的组合太奇妙了，他希望你能告诉他，他总共能画出多少条符合要求的线段？由于答案可能过大，所以请你对1,000,000,007 （1e9+7）取模。

【输入格式】

第一行三个正整数 $n, c, k$。

【输出格式】

第一行一个正整数，表示答案。

【样例】

【输入样例1】

5 3 2

【输出样例1】

16

【输入样例2】

6 2 6

【输出样例2】

27906

【数据规模与约定】

对于15%的数据：$n \le 10; c \le 10; k \le 4$ 对于40%的数据：$n \le 1000; c \le 100; k \le 100$ 对于60%的数据：$n \le 100,000; c \le 100; k \le 100,000$ 对于另外5%的数据：$c=1$ 对于另外5%的数据：$c=n$ 对于100%的数据：$n \le 1,000,000; c\le1,000,000; k\le1,000,000$