24670번 - Mountains 다국어

문제

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 in 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$.

입력

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

출력

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

제한

힌트