Enunciado del problema
En cierto concurso de programación, es costumbre jugar al bingo en la fiesta posterior al concurso. Sin embargo, los cartones de bingo que se utilizan en este juego son algo especiales y se crean siguiendo las siguientes condiciones:
- Un cartón de bingo está dividido en una cuadrícula de $N$ filas y $N$ columnas, y en cada casilla hay escrito $1$ entero positivo. Todos esos enteros son distintos entre sí.
- El entero escrito en cada casilla es mayor o igual que $1$ y menor o igual que $M$.
- La suma de los $N \times N$ enteros escritos en el cartón de bingo es $S$.
- Si se observa cualquier columna, los enteros están ordenados en orden ascendente de arriba hacia abajo.
- El entero de cualquier casilla es mayor que cualquier entero situado en cualquier columna a la izquierda de dicha casilla.
A continuación se muestra un ejemplo de cartón de bingo cuando $N = 5$, $M = 50$ y $S = 685$.
Para la fiesta, queremos hacer tantos cartones de bingo que cumplan las condiciones anteriores como sea posible. Sin embargo, no se deben hacer $2$ o más cartones idénticos. Escribe un programa que imprima el resto de dividir entre $100000$ el número máximo de cartones de bingo que se pueden hacer.
Entrada
La entrada consta de $1$ línea que contiene $3$ enteros positivos separados por espacios, que representan el tamaño del cartón de bingo $N$ ($1 \le N \le 7$), el límite superior de los enteros escritos en las casillas $M$ ($1 \le M \le 2000$) y la suma de los enteros escritos en el cartón de bingo $S$ ($1 \le S \le 3000$). En todos los datos de entrada proporcionados, es posible hacer al menos $1$ cartón de bingo que cumpla las condiciones.
Salida
Imprime en $1$ línea el resto de dividir entre $100000$ el número máximo de cartones de bingo que se pueden hacer.
Ejemplo 1
Entrada
3 9 45
Salida
1
Ejemplo 2
Entrada
3 100 50
Salida
7
Ejemplo 3
Entrada
5 50 685
Salida
74501
Nota
Para el Ejemplo $3$, dado que el número máximo de cartones de bingo que se pueden hacer es $642499974501$, se imprime $74501$, que es el resto al dividirlo entre $100000$.