תיאור הבעיה

בתחרות תכנות מסוימת, נהוג לשחק משחק בינגו במסיבה שלאחר התחרות. אולם, כרטיסי הבינגו המשמשים במשחק בינגו זה הם מיוחדים במקצת, ונוצרים בהתאם לתנאים הבאים:

• כרטיס בינגו מחולק לרשת של $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$.