C0724 [SDWC2018]优秀

如果一个数列相邻两项之差的绝对值均为 $1$（我们认为首项和末项也相邻），并且首项是数列中最小的元素之一，那么我们称之为良好数列。

如果一个数列单调不降且长度在 $1$ 到 $n$ 之间，数列中每个数的值在 $1$ 到 $m$ 之间，且重排后能得到至少 $1$ 个至多 $k$ 个良好数列（意思是说将这个数列打乱顺序可以使数列变成良好数列，而且能得到的不同的良好数列的数量在 $1$ 到 $k$ 之间，两个数列不同当且仅当存在某一位置上的数不同），那么我们称之为优秀数列。

给出 $n$、$m$、$k$，求优秀数列的个数。

答案对 $10^9 + 7$ 取模 。

样例输入 1

1 1 1

样例输出 1

0

样例输入 2

3 3 3

样例输出 2

2

样例输入 3

28 15 34

样例输出 3

54737