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