Bingo Game

At a certain programming contest, there is an unusual custom of playing a bingo game at the after-party. The "bingo card" used here is different from an ordinary bingo card: every cell must be filled so that all of the following conditions hold.

• The bingo card is an $N \times N$ grid of cells, and each cell contains one integer. All of the integers are distinct.
• Each integer is between $1$ and $M$ inclusive.
• The sum of all $N \times N$ integers is $S$.
• In every column the values increase from top to bottom (each column is in ascending order).
• The integer in any cell must be greater than every integer in the columns to its left.

For example, when $N = 5$, $M = 50$, and $S = 685$, at least one bingo card satisfying these conditions exists. (Reading any column from top to bottom gives increasing values, and every value in a column is larger than all values in the columns to its left.)

Because many people want to attend the after-party, you want to make as many bingo cards as possible. However, everyone wants their own card, so no two cards may be identical. Print the maximum number of distinct bingo cards you can make, taken modulo $100000$.

The input consists of one line containing three integers $N$, $M$, and $S$ separated by spaces: the card size $N$ ($1 \le N \le 7$), the maximum integer allowed in a cell $M$ ($1 \le M \le 2000$), and the total sum of the integers on the card $S$ ($1 \le S \le 3000$).

For every given input, it is guaranteed that at least one bingo card satisfying the conditions can be made.

Print, on a single line, the maximum number of distinct bingo cards that can be made, taken modulo $100000$.

For example, when $N = 5$, $M = 50$, and $S = 685$, the total number of bingo cards that can be made is $642499974501$, and $642499974501 \bmod 100000 = 74501$.