Một cuộc thi lập trình có truyền thống tổ chức trò chơi bingo trong buổi giao lưu sau cuộc thi. Những tấm thẻ bingo dùng trong trò chơi này khá đặc biệt và phải thỏa mãn tất cả các điều kiện sau:

• Mỗi thẻ gồm \(N\) hàng và \(N\) cột. Mỗi ô chứa một số nguyên dương và tất cả \(N^2\) số trên thẻ đôi một khác nhau.
• Mỗi số trên thẻ nằm trong khoảng từ \(1\) đến \(M\).
• Tổng tất cả các số trên thẻ bằng \(S\).
• Trong mỗi cột, các số tăng dần từ trên xuống dưới.
• Số trong mỗi ô lớn hơn mọi số thuộc bất kỳ cột nào nằm bên trái cột chứa ô đó.

Ban tổ chức muốn làm nhiều thẻ thỏa mãn các điều kiện trên nhất có thể, nhưng không được làm hai thẻ giống hệt nhau.

Yêu cầu

Cho \(N\), \(M\), \(S\). Hãy tính số thẻ bingo khác nhau có thể tạo ra và in phần dư của số đó khi chia cho \(100\,000\).

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa ba số nguyên dương \(N\), \(M\), \(S\), cách nhau bởi dấu cách. Trong đó, \(N\) là kích thước thẻ, \(M\) là giới hạn trên của các số trên thẻ, và \(S\) là tổng các số trên thẻ.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên, là phần dư của số thẻ bingo khác nhau có thể tạo ra khi chia cho \(100\,000\).

Ràng buộc

• \(1\le N\le7\).
• \(1\le M\le2\,000\).
• \(1\le S\le3\,000\).
• Với mỗi bộ dữ liệu, luôn có ít nhất một thẻ bingo thỏa mãn các điều kiện.

Chấm điểm

Bài có \(4\) bộ dữ liệu chấm, mỗi bộ \(5\) điểm, tổng cộng \(20\) điểm.

Ví dụ

3 9 45

1

3 100 50

7

5 50 685

74501

Có \(642\,499\,974\,501\) thẻ khác nhau thỏa mãn dữ liệu của ví dụ \(3\). Phần dư khi chia số này cho \(100\,000\) là \(74501\).