نص المسألة

في إحدى مسابقات البرمجة، جرت العادة على لعب لعبة البينغو في الحفلة التي تلي المسابقة. غير أن بطاقات البينغو المستخدمة في هذه اللعبة مميزة بعض الشيء، ويتم إنشاؤها وفق الشروط التالية:

• تُقسَّم بطاقة البينغو إلى شبكة من $N$ صفوف و$N$ أعمدة، ويُكتب في كل خلية عدد صحيح موجب واحد ($1$). جميع هذه الأعداد الصحيحة مختلفة.
• العدد الصحيح المكتوب في كل خلية لا يقل عن $1$ ولا يزيد عن $M$.
• مجموع الأعداد الصحيحة البالغ عددها $N \times N$ والمكتوبة على بطاقة البينغو يساوي $S$.
• عند النظر إلى أي عمود، تكون الأعداد الصحيحة مرتبة ترتيبًا تصاعديًا من الأعلى إلى الأسفل.
• العدد الصحيح في أي خلية أكبر من أي عدد صحيح موجود في أي عمود يقع إلى يسار تلك الخلية.

فيما يلي مثال على بطاقة بينغو عندما تكون $N = 5$ و$M = 50$ و$S = 685$.

من أجل الحفلة، نريد صنع أكبر عدد ممكن من بطاقات البينغو التي تحقق الشروط السابقة. ولكن لا يجوز صنع بطاقتين ($2$) متطابقتين أو أكثر. اكتب برنامجًا يطبع باقي قسمة أكبر عدد ممكن من بطاقات البينغو التي يمكن صنعها على $100000$.

المدخلات

تتكون المدخلات من سطر واحد ($1$) يحتوي على $3$ أعداد صحيحة موجبة مفصولة بمسافات، تمثل حجم بطاقة البينغو $N$ ($1 \le N \le 7$)، والحد الأعلى للأعداد الصحيحة المكتوبة في الخلايا $M$ ($1 \le M \le 2000$)، ومجموع الأعداد الصحيحة المكتوبة على بطاقة البينغو $S$ ($1 \le S \le 3000$). في جميع بيانات الإدخال المعطاة، يمكن صنع بطاقة بينغو واحدة ($1$) على الأقل تحقق الشروط.

المخرجات

اطبع في سطر واحد ($1$) باقي قسمة أكبر عدد من بطاقات البينغو التي يمكن صنعها على $100000$.

مثال 1

المدخلات

3 9 45

المخرجات

1

مثال 2

المدخلات

3 100 50

المخرجات

7

مثال 3

المدخلات

5 50 685

المخرجات

74501

ملاحظة

بالنسبة للمثال $3$، بما أن أكبر عدد من بطاقات البينغو التي يمكن صنعها هو $642499974501$، فإننا نطبع $74501$، وهو باقي القسمة على $100000$.