No tag edit access

E. Yaroslav and Arrangements

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYaroslav 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:

- The elements in it do not decrease (
*b*_{i}≤*b*_{i + 1}). - If the inequalities 1 ≤
*r*≤*n*and 1 ≤*b*_{i}≤*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 1000000007 (10^{9} + 7).

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 1000000007 (10^{9} + 7).

Examples

Input

1 1 1

Output

0

Input

3 3 3

Output

2

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/24/2017 23:15:21 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|