# E. Yaroslav and Arrangements Round 182

time limit per test 3 seconds
memory limit per test 256 megabytes

Yaroslav calls an array of r integers a1, a2, …, ar 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 $$a_1 = \min _{i=1}^r a_i$$.

An array of integers $$b_1, b_2, …, b_r$$ is called great, if it meets the following conditions:

The elements in it do not decrease ($$b_i \le b_{i+1}$$).
If the inequalities 1 ≤ r ≤ n and 1 ≤ bi ≤ m hold.
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 1,000,000,007.

Two arrays are considered distinct if there is a position in which they have distinct numbers.

## Input

The single line contains three integers n, m, k (1 ≤ n, m, k ≤ 100).

## Output

In a single line print the remainder after dividing the answer to the problem by number 1,000,000,007.

## Examples

### input

3 3 3


### output

2


## Solution

1. 我们必须清楚当前最大数是多少 这样才知道下一个应该放什么 记为i
2. 我们必须清楚放了多少个数 这样才知道有多少空位置还可以放 记为j
3. 我们必须清楚当前最大数出现了多少次k 这样才会不重不漏的统计方案（考虑将来放的和这k个位置的关系即可）
4. 我们必须清楚当前放入这些之后会形成多少个不同的a数列（题目要求小于等于K） 记为l

~~不~~显然的，我们只需要记录这4个状态就好了。

## Code

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, K;
int C[105][105];
int f[55][55][55][105], ans;
const int P = 1000000007;
typedef long long LL;
void inc(int &x, int val) {
x = (x + val) % P;
}
int main() {
scanf("%d %d %d", &n, &m, &K);
n >>= 1;

C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; ++j)
C[i][j] = min(233, C[i-1][j-1] + C[i-1][j]);
f[1][i][i][1] = 1;
}

int mi = min(n, m);
for (int i = 1; i <= mi; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= j; ++k)
for (int l = 1; l <= K; ++l) {
inc(ans, LL(f[i][j][k][l]) * LL(m-i) % P);
for (int x = 1; x <= n-j; ++x) {
int l1 = LL(l) * C[k+x-1][x-1] % P;
if (l1 > K) break;
inc(f[i+1][j+x][x][l1], f[i][j][k][l]);
}
}
printf("%d", ans);
}