Mountains

Time limit1sMemory limit256 MB

Summary

Count n by m grids of non-negative heights, each at most k, whose maximum-weight monotone path from (1,1) to (n,m) has total sum at most k.

Level: Hard9 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Damir is climbing mountains. The mountain map can be represented as an $n \times m$ grid, in which a cell at the intersection of row $i$ and column $j$ is denoted as $(i, j)$ . The height of the peak in cell $(i, j)$ is equal to a non-negative integer $a_{i, j}$ . Damir starts his journey on the peak in cell $(1, 1)$ aiming to reach the peak in cell $(n, m)$ . If Damir is on the peak in cell $(i, j)$ , then he can go either to the peak in cell $(i + 1, j)$ or to the peak in cell $(i, j + 1)$ . Of course, he cannot go outside the boundaries of the map. To make the journey more interesting, he chooses the path with the largest sum of peak heights (kind of total climb).

Damir loves combinatorics, and he became curious: how many $n \times m$ maps are there such that the sum of peak heights on his path does not exceed $k$ ? As the answer may be large, find it modulo $10^9 + 7$ .

Input

The only line of input contains three integers, $n$ , $m$ , and $k$ ( $1 \le n, m, k \le 100$ ).

Output

Print the answer modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
1 1 1
```
Expected output
```
2
```
Example 2
Input
```
2 2 2
```
Expected output
```
20
```
Example 3
Input
```
2 3 4
```
Expected output
```
490
```