Verkefnalýsing

Í tiltekinni forritunarkeppni er hefð fyrir því að spila bingó í veislunni eftir keppnina. Hins vegar eru bingóspjöldin sem notuð eru í þessum bingóleik nokkuð sérstök og eru búin til samkvæmt eftirfarandi skilyrðum:

• Bingóspjaldi er skipt í $N$ raðir og $N$ dálka af reitum, og í hvern reit er skrifuð $1$ jákvæð heiltala. Allar þessar heiltölur eru ólíkar.
• Heiltalan sem skrifuð er í hvern reit er að minnsta kosti $1$ og í mesta lagi $M$.
• Summa þeirra $N \times N$ heiltalna sem skrifaðar eru á bingóspjaldið er $S$.
• Sama hvaða dálkur er skoðaður, þá raðast heiltölurnar í hækkandi röð ofan frá og niður.
• Heiltalan í hverjum reit er stærri en sérhver heiltala í öllum dálkum vinstra megin við þann reit.

Hér fyrir neðan er dæmi um bingóspjald þegar $N = 5$, $M = 50$ og $S = 685$.

Fyrir veisluna viljum við búa til eins mörg bingóspjöld og mögulegt er sem uppfylla skilyrðin hér að ofan. Hins vegar má ekki búa til $2$ eða fleiri eins spjöld. Skrifaðu forrit sem prentar út afganginn þegar hámarksfjölda bingóspjalda sem hægt er að búa til er deilt með $100000$.

Inntak

Inntakið samanstendur af $1$ línu sem inniheldur $3$ jákvæðar heiltölur aðskildar með bilum, sem tákna stærð bingóspjaldsins $N$ ($1 \le N \le 7$), efri mörk heiltalnanna sem skrifaðar eru í reitina $M$ ($1 \le M \le 2000$), og summu heiltalnanna sem skrifaðar eru á bingóspjaldið $S$ ($1 \le S \le 3000$). Í öllum gefnum inntaksgögnum er hægt að búa til að minnsta kosti $1$ bingóspjald sem uppfyllir skilyrðin.

Úttak

Skrifaðu út í $1$ línu afganginn þegar hámarksfjölda bingóspjalda sem hægt er að búa til er deilt með $100000$.

Dæmi 1

Inntak

3 9 45

Úttak

1

Dæmi 2

Inntak

3 100 50

Úttak

7

Dæmi 3

Inntak

5 50 685

Úttak

74501

Athugasemd

Fyrir Dæmi $3$, þar sem hámarksfjöldi bingóspjalda sem hægt er að búa til er $642499974501$, skal skrifa út $74501$, sem er afgangurinn þegar deilt er með $100000$.