← 返回题目列表

Codeforces · 301/E

E. 雅罗斯拉夫和安排

中文机器翻译题面 查看原题

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