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$.