Oppgavebeskrivelse
I en bestemt programmeringskonkurranse er det tradisjon å spille bingo på festen etter konkurransen. Bingobrettene som brukes i dette bingospillet er imidlertid litt spesielle, og lages etter følgende betingelser:
- Et bingobrett er delt inn i et rutenett med $N$ rader og $N$ kolonner, og i hver rute står det $1$ positivt heltall. Alle disse heltallene er forskjellige.
- Heltallet som står i hver rute er minst $1$ og høyst $M$.
- Summen av de $N \times N$ heltallene som står på bingobrettet er $S$.
- Uansett hvilken kolonne man ser på, er heltallene ordnet i stigende rekkefølge ovenfra og ned.
- Heltallet i enhver rute er større enn ethvert heltall i enhver kolonne til venstre for denne ruten.
Nedenfor er et eksempel på et bingobrett når $N = 5$, $M = 50$ og $S = 685$.
Til festen ønsker vi å lage så mange bingobrett som mulig som oppfyller betingelsene ovenfor. Vi har imidlertid ikke lov til å lage $2$ eller flere identiske brett. Skriv et program som skriver ut resten når det maksimale antallet bingobrett som kan lages, deles på $100000$.
Inndata
Inndata består av $1$ linje som inneholder $3$ positive heltall atskilt med mellomrom, som representerer størrelsen på bingobrettet $N$ ($1 \le N \le 7$), den øvre grensen for heltallene skrevet i rutene $M$ ($1 \le M \le 2000$), og summen av heltallene skrevet på bingobrettet $S$ ($1 \le S \le 3000$). I alle gitte inndata er det mulig å lage minst $1$ bingobrett som oppfyller betingelsene.
Utdata
Skriv ut på $1$ linje resten når det maksimale antallet bingobrett som kan lages, deles på $100000$.
Eksempel 1
Inndata
3 9 45
Utdata
1
Eksempel 2
Inndata
3 100 50
Utdata
7
Eksempel 3
Inndata
5 50 685
Utdata
74501
Merknad
For Eksempel $3$, siden det maksimale antallet bingobrett som kan lages er $642499974501$, skal det skrives ut $74501$, som er resten ved divisjon med $100000$.