Yaroslav 调用 r 整数数组 a1, a2, ..., ar 好,如果它满足以下条件: |a1 - a2| = 1, |a2 - a3| = 1, ..., |ar - 1 - ar| = 1, |ar - a1| = 1,此时 $$a_{1} = \min_{i=1}^{r} a_{i}$$。
整数数组 b1, b2, ..., br 如果满足以下条件,则称为 Great 数组:
1、里面的元素不减少(bi ≤ bi + 1)。
2. 如果不等式 1 ≤ r ≤ n 和 1 ≤ bi ≤ m 成立。
3. 如果我们可以重新排列它的元素并得到至少一个且最多 k 个不同的好数组。
Yaroslav 有三个整数 n、m、k。他需要统计不同大阵的数量。帮助雅罗斯拉夫!由于答案可能相当大,因此打印除以 1000000007 (109 + 7) 后的余数。
如果两个数组在某个位置具有不同的数字,则认为它们是不同的。
输入
单行包含三个整数 n、m、k (1 ≤ n、m、k ≤ 100)。
输出
在一行中打印问题答案除以数字 1000000007 (109 + 7) 后的余数。
示例
输入 #1
1 1 1
输出 #1
0
输入 #2
3 3 3
输出 #2
2