Problem Description

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

• The bingo card is divided into an $ N $ by $ N $ grid, and each cell contains one positive integer. All these integers are distinct.
• The integers written in the cells are between $ 1 $ and $ M $ inclusive.
• The sum of the $N \times N$ integers on the bingo card is $ S $.
• When looking at any column, the integers are sorted in ascending order from top to bottom.
• Any integer in a cell is larger than any integer in the columns to its left.

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

We want to create as many bingo cards as possible that satisfy the above conditions. However, we must not create more than one copy of the same card. Write a program that outputs the maximum number of bingo cards that can be created, modulo $ 100,000 $.

Input Format

The input consists of one line containing three positive integers separated by spaces: the size of the bingo card $ N $ ($1 \leq N \leq 7$), the upper limit of the integers in the cells $ M $ ($1 \leq M \leq 2,000$), and the sum of the integers on the bingo card $ S $ ($1 \leq S \leq 3,000$). For any given input, it is guaranteed that at least one bingo card can be created that satisfies the conditions.

Output Format

Output the maximum number of bingo cards that can be created, modulo $ 100,000 $.

Sample Input and Output

Sample Input #1

3 9 45

Sample Output #1

1

Sample Input #2

3 100 50

Sample Output #2

7

Sample Input #3

5 50 685

Sample Output #3

74501

Notes/Hints

Sample Explanation 1

Sample Explanation 2

Sample Explanation 3

For the third input example, the maximum number of bingo cards that can be created is $ 642,499,974,501 $, so the output should be the remainder when divided by $ 100,000 $, which is $ 74,501 $.

见题面 Input 部分

见题面 Output 部分