Yaroslav and Arrangements

3000ms

262144K

Description:

Yaroslav calls an array of r integers a₁, a₂, ..., a_r good, if it meets the following conditions: |a₁ - a₂| = 1, |a₂ - a₃| = 1, ..., |a_r - 1 - a_r| = 1, |a_r - a₁| = 1, at that $\text{[math]}$ .

An array of integers b₁, b₂, ..., 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⁹ + 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⁹ + 7).

Sample Input:

1 1 1

Sample Output:

Sample Input:

3 3 3

Sample Output:

Informação

Provedor Codeforces

Código CF301E