Treść zadania
Podczas pewnego konkursu programistycznego tradycją jest gra w bingo na spotkaniu integracyjnym po zawodach. Jednak karty do bingo używane w tej grze są nieco nietypowe i tworzy się je zgodnie z następującymi warunkami:
- Karta do bingo jest podzielona na siatkę o $N$ wierszach i $N$ kolumnach, a w każdym polu zapisana jest $1$ dodatnia liczba całkowita. Wszystkie te liczby całkowite są parami różne.
- Liczba całkowita zapisana w każdym polu jest nie mniejsza niż $1$ i nie większa niż $M$.
- Suma $N \times N$ liczb całkowitych zapisanych na karcie do bingo wynosi $S$.
- W każdej kolumnie liczby całkowite są uporządkowane rosnąco od góry do dołu.
- Liczba całkowita w dowolnym polu jest większa od każdej liczby całkowitej znajdującej się w dowolnej kolumnie na lewo od tego pola.
Poniżej przedstawiono przykład karty do bingo dla $N = 5$, $M = 50$ oraz $S = 685$.
Na spotkanie integracyjne chcemy przygotować jak najwięcej kart do bingo spełniających powyższe warunki. Nie wolno jednak utworzyć $2$ ani więcej identycznych kart. Napisz program, który wypisze resztę z dzielenia maksymalnej liczby kart do bingo, jakie można utworzyć, przez $100000$.
Wejście
Wejście składa się z $1$ wiersza zawierającego $3$ dodatnie liczby całkowite oddzielone spacjami, oznaczające kolejno rozmiar karty do bingo $N$ ($1 \le N \le 7$), górne ograniczenie liczb całkowitych zapisanych w polach $M$ ($1 \le M \le 2000$) oraz sumę liczb całkowitych zapisanych na karcie do bingo $S$ ($1 \le S \le 3000$). Dla wszystkich podanych danych wejściowych można utworzyć co najmniej $1$ kartę do bingo spełniającą warunki.
Wyjście
Wypisz w $1$ wierszu resztę z dzielenia maksymalnej liczby kart do bingo, jakie można utworzyć, przez $100000$.
Przykład 1
Wejście
3 9 45
Wyjście
1
Przykład 2
Wejście
3 100 50
Wyjście
7
Przykład 3
Wejście
5 50 685
Wyjście
74501
Uwaga
Dla Przykładu $3$ maksymalna liczba kart do bingo, jakie można utworzyć, wynosi $642499974501$, zatem należy wypisać $74501$, czyli resztę z dzielenia tej liczby przez $100000$.