Yaroslav and Arrangements

题意翻译

【问题描述】 如果一个数列相邻两项之差的绝对值均为 1（我们认为首项和末项也相 邻），并且首项是数列中最小的元素之一，那么我们称之为良好数列。 如果一个数列单调不降且长度在 1 到 n 之间，数列中每个数的值在 1 到 m 之间，且重排后能得到至少 1 个至多 k 个良好数列，那么我们称之为优秀数列。 给出 n、m、k，求优秀数列的个数。 答案对 1000000007 取模 【输入格式】 单独一行三个整数 n，m，k 【输出格式】 单独一行输出答案 Translated by @Kirito_Rivaille

题目描述

Yaroslav calls an array of $ r $ integers $ a_{1},a_{2},...,a_{r} $ good, if it meets the following conditions: $ |a_{1}-a_{2}|=1,|a_{2}-a_{3}|=1,...,|a_{r-1}-a_{r}|=1,|a_{r}-a_{1}|=1 $ , at that . An array of integers $ b_{1},b_{2},...,b_{r} $ is called great, if it meets the following conditions: 1. The elements in it do not decrease $ (b_{i}<=b_{i+1}) $ . 2. If the inequalities $ 1<=r<=n $ and $ 1<=b_{i}<=m $ hold. 3. If we can rearrange its elements and get at least one and at most $ k $ distinct good arrays. Yaroslav has three integers $ n,m,k $ . He needs to count the number of distinct great arrays. Help Yaroslav! As the answer may be rather large, print the remainder after dividing it by $ 1000000007 $ $ (10^{9}+7) $ . Two arrays are considered distinct if there is a position in which they have distinct numbers.

输入输出格式

输入格式

The single line contains three integers $ n $ , $ m $ , $ k $ $ (1<=n,m,k<=100) $ .

输出格式

In a single line print the remainder after dividing the answer to the problem by number $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

1 1 1

输出样例 #1

0

输入样例 #2

3 3 3

输出样例 #2

2