Умова задачі
На одному змаганні з програмування є традиція грати в бінго на вечірці після контесту. Проте картки для бінго, які використовуються в цій грі, дещо незвичайні й створюються за такими правилами:
- Картка для бінго поділена на таблицю з $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$.