Đề bài

Tại một kỳ thi lập trình nọ, có thông lệ là chơi trò chơi bingo trong bữa tiệc giao lưu sau kỳ thi. Tuy nhiên, các thẻ bingo được sử dụng trong trò chơi bingo này hơi đặc biệt và được tạo ra theo các điều kiện sau:

• Một thẻ bingo được chia thành lưới gồm $N$ hàng và $N$ cột, và mỗi ô được ghi $1$ số nguyên dương. Tất cả các số nguyên đó đều đôi một khác nhau.
• Số nguyên ghi trong mỗi ô lớn hơn hoặc bằng $1$ và nhỏ hơn hoặc bằng $M$.
• Tổng của $N \times N$ số nguyên ghi trên thẻ bingo là $S$.
• Xét bất kỳ cột nào, các số nguyên đều được sắp xếp theo thứ tự tăng dần từ trên xuống dưới.
• Số nguyên ở bất kỳ ô nào cũng lớn hơn mọi số nguyên nằm ở bất kỳ cột nào bên trái ô đó.

Dưới đây là ví dụ về một thẻ bingo khi $N = 5$, $M = 50$, và $S = 685$.

Để phục vụ cho bữa tiệc, người ta muốn tạo ra càng nhiều thẻ bingo thỏa mãn các điều kiện trên càng tốt. Tuy nhiên, không được tạo ra từ $2$ thẻ giống hệt nhau trở lên. Hãy viết chương trình in ra số dư khi chia số lượng thẻ bingo tối đa có thể tạo được cho $100000$.

Dữ liệu vào

Dữ liệu vào gồm $1$ dòng chứa $3$ số nguyên dương cách nhau bởi dấu cách, lần lượt biểu thị kích thước của thẻ bingo $N$ ($1 \le N \le 7$), cận trên của các số nguyên ghi trong các ô $M$ ($1 \le M \le 2000$), và tổng các số nguyên ghi trên thẻ bingo $S$ ($1 \le S \le 3000$). Trong mọi dữ liệu vào được cho, luôn có thể tạo được ít nhất $1$ thẻ bingo thỏa mãn điều kiện.

Kết quả

In ra trên $1$ dòng số dư khi chia số lượng thẻ bingo tối đa có thể tạo được cho $100000$.

Ví dụ 1

Dữ liệu vào

3 9 45

Kết quả

1

Ví dụ 2

Dữ liệu vào

3 100 50

Kết quả

7

Ví dụ 3

Dữ liệu vào

5 50 685

Kết quả

74501

Chú thích

Đối với Ví dụ $3$, vì số lượng thẻ bingo tối đa có thể tạo được là $642499974501$, nên chương trình cần in ra $74501$, là số dư khi chia cho $100000$.