Problembeskrivning

Vid en viss programmeringstävling är det sed att spela bingo på festen efter tävlingen. Bingobrickorna som används i detta bingospel är dock lite speciella och skapas enligt följande villkor:

• En bingobricka är indelad i ett rutnät med $N$ rader och $N$ kolumner, och i varje ruta står $1$ positivt heltal. Alla dessa heltal är olika.
• Heltalet som står i varje ruta är minst $1$ och högst $M$.
• Summan av de $N \times N$ heltal som står på bingobrickan är $S$.
• Oavsett vilken kolumn man tittar på är heltalen ordnade i stigande ordning uppifrån och ner.
• Heltalet i varje ruta är större än varje heltal i alla kolumner till vänster om den rutan.

Nedan visas ett exempel på en bingobricka när $N = 5$, $M = 50$ och $S = 685$.

Till festen vill vi göra så många bingobrickor som möjligt som uppfyller ovanstående villkor. Vi får dock inte göra $2$ eller fler likadana brickor. Skriv ett program som skriver ut resten när det maximala antalet bingobrickor som kan göras divideras med $100000$.

Indata

Indata består av $1$ rad som innehåller $3$ positiva heltal åtskilda av blanksteg, vilka representerar bingobrickans storlek $N$ ($1 \le N \le 7$), den övre gränsen för heltalen i rutorna $M$ ($1 \le M \le 2000$) samt summan av heltalen på bingobrickan $S$ ($1 \le S \le 3000$). I all given indata är det möjligt att göra minst $1$ bingobricka som uppfyller villkoren.

Utdata

Skriv på $1$ rad ut resten när det maximala antalet bingobrickor som kan göras divideras med $100000$.

Exempel 1

Indata

3 9 45

Utdata

1

Exempel 2

Indata

3 100 50

Utdata

7

Exempel 3

Indata

5 50 685

Utdata

74501

Kommentar

För Exempel $3$ är det maximala antalet bingobrickor som kan göras $642499974501$, så programmet ska skriva ut $74501$, vilket är resten vid division med $100000$.