โจทย์ปัญหา

ในการแข่งขันเขียนโปรแกรมแห่งหนึ่ง มีธรรมเนียมการเล่นเกมบิงโกในงานเลี้ยงสังสรรค์หลังจบการแข่งขัน อย่างไรก็ตาม การ์ดบิงโกที่ใช้ในเกมบิงโกนี้ค่อนข้างพิเศษ และถูกสร้างขึ้นตามเงื่อนไขต่อไปนี้:

• การ์ดบิงโกถูกแบ่งออกเป็นตารางขนาด $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$ ใบเสมอ

ข้อมูลส่งออก

แสดงเศษเหลือจากการหารจำนวนการ์ดบิงโกมากที่สุดที่สามารถสร้างได้ด้วย $100000$ ใน $1$ บรรทัด

ตัวอย่าง 1

ข้อมูลนำเข้า

3 9 45

ข้อมูลส่งออก

1

ตัวอย่าง 2

ข้อมูลนำเข้า

3 100 50

ข้อมูลส่งออก

7

ตัวอย่าง 3

ข้อมูลนำเข้า

5 50 685

ข้อมูลส่งออก

74501

หมายเหตุ

สำหรับตัวอย่างที่ $3$ เนื่องจากจำนวนการ์ดบิงโกมากที่สุดที่สามารถสร้างได้คือ $642499974501$ ใบ จึงแสดงค่า $74501$ ซึ่งเป็นเศษเหลือเมื่อหารด้วย $100000$