Есептің шарты

Белгілі бір программалау жарысында жарыستان кейінгі кеште бинго ойынын ойнау дәстүрі бар. Алайда бұл бинго ойынында қолданылатын бинго карточкалары сәл ерекше және келесі шарттарға сәйкес жасалады:

• Бинго карточкасы $N$ жол мен $N$ бағаннан тұратын торкөздерге бөлінген, және әр ұяшыққа $1$ оң бүтін саннан жазылған. Ол бүтін сандардың барлығы өзара әртүрлі.
• Әр ұяшықта жазылған бүтін сан кемінде $1$ және көп дегенде $M$ болады.
• Бинго карточкасында жазылған $N \times N$ бүтін санның қосындысы $S$-ке тең.
• Кез келген бағанға қарасақ, бүтін сандар жоғарыдан төмен қарай өсу ретімен орналасқан.
• Кез келген ұяшықтағы бүтін сан сол ұяшықтың сол жағындағы кез келген бағандағы кез келген бүтін саннан үлкен.

Төменде $N = 5$, $M = 50$, $S = 685$ болған кездегі бинго карточкасының мысалы келтірілген.

Кешке арнап жоғарыдағы шарттарды қанағаттандыратын бинго карточкаларын мүмкіндігінше көп жасағымыз келеді. Бірақ бірдей карточканы $2$ немесе одан көп дана етіп жасауға болмайды. Жасауға болатын бинго карточкаларының ең көп санын $100000$-ға бөлгендегі қалдықты шығаратын программа жазыңыз.

Кіріс деректер

Кіріс деректер бос орын арқылы бөлінген $3$ оң бүтін саннан тұратын $1$ жолдан құралған: олар бинго карточкасының өлшемін $N$ ($1 \le N \le 7$), ұяшықтарға жазылатын бүтін сандардың жоғарғы шегін $M$ ($1 \le M \le 2000$) және бинго карточкасында жазылған бүтін сандардың қосындысын $S$ ($1 \le S \le 3000$) білдіреді. Берілген барлық кіріс деректерде шарттарды қанағаттандыратын кемінде $1$ бинго карточкасын жасауға болады.

Шығыс деректер

Жасауға болатын бинго карточкаларының ең көп санын $100000$-ға бөлгендегі қалдықты $1$ жолда шығарыңыз.

1-мысал

Кіріс деректер

3 9 45

Шығыс деректер

1

2-мысал

Кіріс деректер

3 100 50

Шығыс деректер

7

3-мысал

Кіріс деректер

5 50 685

Шығыс деректер

74501

Ескертпе

$3$-мысал үшін жасауға болатын бинго карточкаларының ең көп саны $642499974501$ болғандықтан, оны $100000$-ға бөлгендегі қалдық $74501$ санын шығарамыз.