测试数据来自 system/1878

描述

小岛还依稀记得, 6年前他生日的那一天.
那一次生日他在vijos上举办了第一次属于自己的比赛.
赛后, 小岛邀请了vijos上很多小伙伴们来参加自己的生日聚餐. 有可爱的十八居士, 有萌萌哒教主, 有好厉害好厉害的cgy, 有负责比赛管理的lk, 还有很多其它的小伙伴们.

那一次他准备了一张有 N 个位子的圆形桌子, 而一共陆陆续续来了 K 位客人.
位子从0到N-1依次编号, 相邻编号的位子是相邻的, 此外: 0号位子与N-1号位子相邻.

K位客人依次抵达, 每次来了一位新的客人, 小岛就需要安排TA坐在某一个空着的位子上, 并且之后不会再移动(也不会离开).
小岛认为如果有连续若干个位子上有人, 那么他们就组成了一个温馨的"团体", 这是有益的.

如果"团体"的个数太多, 会严重破坏聚餐的氛围.
小岛希望任何时刻, "团体"的个数都不超过 G 个.

举个例子来说, 当 N = 4, K = 3, G = 1 的时候, 我们用 A B C 来表示依次前往的三位客人. (用'.'来表示空座位)
那么 "ABC." 就表示 A B C 分别坐在了编号为 0 1 2 的座位上.
但是 ".ABC" 或者 "C.AB" 都被认为是不同的情况. 换句话说: 客人们即便座位顺序相同但是所选择的座位编号不同, 也被认为是不同的.

因为 G = 1, 所以 "ABC.", "C.AB", "B.CA", 和 ".BAC" 都被认为是合法的方案. 但是 "A.BC" 或 ".ACB" 则都不是合法的方案, 因为若只来了 A B, 且 C 还没有到来, 那么这样的座位安排就会导致出现两个 "团体", 这是不符合要求的 (换句话说, 对于 "A.BC" 因为A B C是依次到达的, 所以会出现一个中间状态 "A.B." , 这时就出现了两个 "团体" ).

现在, 你将给定 N , K , G , 你需要告诉小岛有多少合法的座位安排方式. 反馈统计的个数 mod 1,000,000,007.

格式

输入格式

第一行有一个整数 N, 2 <= N <= 2000.
第二行有一个整数 K, 1 <= K <= N.
第三行有一个整数 G, 1 <= G <= K.

输出格式

输出只有一行, 有一个整数即为答案.

样例1

样例输入1

4
2
1

样例输出1

8

样例2

样例输入2

5
4
2

样例输出2

120

样例3

样例输入3

42
23
7

样例输出3

917668006

限制

对于25%的数据: 2 <= N <= 5
对于50%的数据: 2 <= N <= 100
对于100%的数据: 2 <= N <= 2000, 1 <= K <= N, 1 <= G <= K.

每一个测试点的时间限制为0.3秒