Énoncé du problème
Lors d'un certain concours de programmation, il est de coutume de jouer au bingo pendant la réception qui suit le concours. Cependant, les grilles de bingo utilisées dans ce jeu sont un peu particulières et sont fabriquées selon les conditions suivantes :
- Une grille de bingo est divisée en $N$ lignes et $N$ colonnes de cases, et $1$ entier strictement positif est inscrit dans chaque case. Tous ces entiers sont deux à deux distincts.
- L'entier inscrit dans chaque case est supérieur ou égal à $1$ et inférieur ou égal à $M$.
- La somme des $N \times N$ entiers inscrits sur la grille de bingo vaut $S$.
- Dans n'importe quelle colonne, les entiers sont rangés par ordre strictement croissant de haut en bas.
- L'entier inscrit dans n'importe quelle case est strictement supérieur à n'importe quel entier situé dans une colonne à gauche de cette case.
Voici ci-dessous un exemple de grille de bingo lorsque $N = 5$, $M = 50$ et $S = 685$.
Pour la réception, on souhaite fabriquer autant de grilles de bingo respectant les conditions ci-dessus que possible. Toutefois, il est interdit de fabriquer $2$ grilles identiques ou plus. Écrivez un programme qui affiche le reste de la division par $100000$ du nombre maximal de grilles de bingo pouvant être fabriquées.
Entrée
L'entrée est constituée de $1$ ligne contenant $3$ entiers strictement positifs séparés par des espaces, représentant respectivement la taille de la grille de bingo $N$ ($1 \le N \le 7$), la borne supérieure des entiers inscrits dans les cases $M$ ($1 \le M \le 2000$) et la somme des entiers inscrits sur la grille de bingo $S$ ($1 \le S \le 3000$). Pour toutes les données d'entrée fournies, il est possible de fabriquer au moins $1$ grille de bingo respectant les conditions.
Sortie
Affichez sur $1$ ligne le reste de la division par $100000$ du nombre maximal de grilles de bingo pouvant être fabriquées.
Exemple 1
Entrée
3 9 45
Sortie
1
Exemple 2
Entrée
3 100 50
Sortie
7
Exemple 3
Entrée
5 50 685
Sortie
74501
Note
Pour l'Exemple $3$, comme le nombre maximal de grilles de bingo pouvant être fabriquées est $642499974501$, il faut afficher $74501$, qui est le reste de sa division par $100000$.