题目描述

有一张 $n$ 个位置的圆桌，圆桌位置带标号，现在有 $m$ 个不同的人按一定顺序到来并且坐下。

我们将左右相邻的人为联通的。如果一个人与另一个人直接或者间接联通，我们称他们在同一个联通块。

要求每一个时刻最多不超过 $k$ 个联通块，问有多少种不同安排位置的方案（同一个人坐的位置标号不同算不同方案）。

对 $10^9+7$ 取模。

输入格式

一行三个正整数 $n,m,k$。$(1\le k\le m\le n\le 2000,n>1)$

输出格式

一行一个数表示答案。

样例

样例输入 1

3 2 1

样例输出 1

6

样例输入 2

4 2 1

样例输出 2

8

样例输入 3

2 2 1

样例输出 3

2

样例输入 4

5 4 2

样例输出 4

120

样例输入 5

42 23 7

样例输出 5

917668006