Problem Statement

At a certain programming contest, it is customary to play a bingo game at the post-contest party. However, the bingo cards used in this bingo game are somewhat special and are created according to the following conditions:

• A bingo card is divided into a grid of $N$ rows and $N$ columns, and $1$ positive integer is written in each cell. All of those integers are distinct.
• The integer written in each cell is at least $1$ and at most $M$.
• The sum of the $N \times N$ integers written on the bingo card is $S$.
• Looking at any column, the integers are arranged in ascending order from top to bottom.
• The integer in any cell is greater than any integer in any column to the left of that cell.

Below is an example of a bingo card when $N = 5$, $M = 50$, and $S = 685$.

For the party, we want to make as many bingo cards satisfying the above conditions as possible. However, we must not make $2$ or more identical cards. Write a program to output the remainder when the maximum number of bingo cards that can be made is divided by $100000$.

Input

The input consists of $1$ line containing $3$ positive integers separated by spaces, representing the size of the bingo card $N$ ($1 \le N \le 7$), the upper bound of integers written in the cells $M$ ($1 \le M \le 2000$), and the sum of integers written on the bingo card $S$ ($1 \le S \le 3000$). In all given input data, it is possible to make at least $1$ bingo card satisfying the conditions.

Output

Output on $1$ line the remainder when the maximum number of bingo cards that can be made is divided by $100000$.

Sample 1

Input

3 9 45

Output

1

Sample 2

Input

3 100 50

Output

7

Sample 3

Input

5 50 685

Output

74501

Note

For Sample $3$, since the maximum number of bingo cards that can be made is $642499974501$, output $74501$, which is the remainder when divided by $100000$.