Testo del problema
In una certa gara di programmazione è consuetudine giocare a bingo durante la festa successiva alla gara. Tuttavia, le cartelle del bingo utilizzate in questo gioco sono piuttosto particolari e vengono create secondo le seguenti condizioni:
- Una cartella del bingo è suddivisa in una griglia di $N$ righe e $N$ colonne, e in ogni casella è scritto $1$ intero positivo. Tutti questi interi sono distinti tra loro.
- L'intero scritto in ciascuna casella è compreso tra $1$ e $M$ inclusi.
- La somma degli $N \times N$ interi scritti sulla cartella del bingo è $S$.
- Osservando qualsiasi colonna, gli interi sono disposti in ordine crescente dall'alto verso il basso.
- L'intero in qualsiasi casella è maggiore di qualsiasi intero presente in una qualsiasi colonna a sinistra di tale casella.
Di seguito è riportato un esempio di cartella del bingo per $N = 5$, $M = 50$ e $S = 685$.
Per la festa si vogliono realizzare il maggior numero possibile di cartelle del bingo che soddisfino le condizioni precedenti. Tuttavia, non si devono realizzare $2$ o più cartelle identiche. Scrivi un programma che stampi il resto della divisione per $100000$ del numero massimo di cartelle del bingo che è possibile realizzare.
Input
L'input è costituito da $1$ riga contenente $3$ interi positivi separati da spazi, che rappresentano rispettivamente la dimensione della cartella del bingo $N$ ($1 \le N \le 7$), il limite superiore degli interi scritti nelle caselle $M$ ($1 \le M \le 2000$) e la somma degli interi scritti sulla cartella del bingo $S$ ($1 \le S \le 3000$). In tutti i dati di input forniti è possibile realizzare almeno $1$ cartella del bingo che soddisfi le condizioni.
Output
Stampa su $1$ riga il resto della divisione per $100000$ del numero massimo di cartelle del bingo che è possibile realizzare.
Esempio 1
Input
3 9 45
Output
1
Esempio 2
Input
3 100 50
Output
7
Esempio 3
Input
5 50 685
Output
74501
Nota
Per l'Esempio $3$, poiché il numero massimo di cartelle del bingo che è possibile realizzare è $642499974501$, bisogna stampare $74501$, che è il resto della divisione per $100000$.