序列计数
题号：NC282067
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

现在有一个长度为n的序列。你需要为序列上的每个位置填入范围在[1, m]的数字。

要求：
1. 相邻的两个数字之间差的绝对值小于等于$1$.
2. 出现的数字种类不超过$k$种.

你需要计数有多少种不同的方案数。方案数量对10^9 + 7取模。

输入描述:

一行三个整数n, m, k。其中，1 \le n \le 10^3, 1 \le m \le 10^5, 1 \le k \le 10.

输出描述:

一行一个整数表示答案。
示例1

输入

复制 
2 2 1

输出

复制 
2
示例2

输入

复制 
10 6 2

输出

复制 
5116