Tehtävänanto
Eräässä ohjelmointikilpailussa on tapana pelata bingoa kilpailun jälkeisissä illanistujaisissa. Tässä bingopelissä käytettävät bingokortit ovat kuitenkin hieman erikoisia, ja ne laaditaan seuraavien ehtojen mukaisesti:
- Bingokortti on jaettu $N$ rivin ja $N$ sarakkeen ruudukoksi, ja jokaiseen ruutuun on kirjoitettu $1$ positiivinen kokonaisluku. Kaikki nämä kokonaisluvut ovat keskenään eri suuria.
- Jokaiseen ruutuun kirjoitettu kokonaisluku on vähintään $1$ ja korkeintaan $M$.
- Bingokorttiin kirjoitettujen $N \times N$ kokonaisluvun summa on $S$.
- Tarkasteltiinpa mitä tahansa saraketta, kokonaisluvut ovat siinä nousevassa järjestyksessä ylhäältä alas.
- Jokaisen ruudun kokonaisluku on suurempi kuin mikään kyseisen ruudun vasemmalla puolella olevissa sarakkeissa esiintyvä kokonaisluku.
Alla on esimerkki bingokortista, kun $N = 5$, $M = 50$ ja $S = 685$.
Illanistujaisia varten halutaan valmistaa mahdollisimman monta yllä olevat ehdot täyttävää bingokorttia. Kuitenkaan samaa korttia ei saa valmistaa $2$ tai useampaa kappaletta. Kirjoita ohjelma, joka tulostaa jakojäännöksen, kun valmistettavissa olevien bingokorttien enimmäismäärä jaetaan luvulla $100000$.
Syöte
Syöte koostuu $1$ rivistä, jolla on välilyönnein eroteltuina $3$ positiivista kokonaislukua: bingokortin koko $N$ ($1 \le N \le 7$), ruutuihin kirjoitettavien kokonaislukujen yläraja $M$ ($1 \le M \le 2000$) sekä bingokorttiin kirjoitettujen kokonaislukujen summa $S$ ($1 \le S \le 3000$). Kaikilla annetuilla syötteillä on mahdollista valmistaa vähintään $1$ ehdot täyttävä bingokortti.
Tuloste
Tulosta $1$ riville jakojäännös, kun valmistettavissa olevien bingokorttien enimmäismäärä jaetaan luvulla $100000$.
Esimerkki 1
Syöte
3 9 45
Tuloste
1
Esimerkki 2
Syöte
3 100 50
Tuloste
7
Esimerkki 3
Syöte
5 50 685
Tuloste
74501
Huomautus
Esimerkissä $3$ valmistettavissa olevien bingokorttien enimmäismäärä on $642499974501$, joten tulostetaan $74501$, joka on jakojäännös jaettaessa luvulla $100000$.