题目描述

原题来自：Codeforces Round #182 (Div 1). E. Yaroslav and Arrangements

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

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

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

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

输入格式

单独一行三个整数 $n , m , k$，以单个空格间隔。

输出格式

单独一行输出答案。

1 1 1

0

3 3 3

2

28 15 34

54737

数据范围与提示

对于 $30\%$ 的数据，$n,m,k \leq 8$；

对于 $60\%$ 的数据，$n,m,k \leq 30$；

对于 $100\%$ 的数据，$n,m,k \leq 100$。