Aufgabenstellung

Bei einem bestimmten Programmierwettbewerb ist es Brauch, auf der anschließenden Feier ein Bingospiel zu veranstalten. Allerdings sind die Bingokarten, die bei diesem Bingospiel verwendet werden, etwas speziell und werden nach den folgenden Bedingungen erstellt:

• Eine Bingokarte ist in ein Gitter aus $N$ Zeilen und $N$ Spalten unterteilt, und in jedes Feld ist $1$ positive ganze Zahl eingetragen. Alle diese ganzen Zahlen sind paarweise verschieden.
• Die in ein Feld eingetragene ganze Zahl ist mindestens $1$ und höchstens $M$.
• Die Summe der $N \times N$ auf der Bingokarte eingetragenen ganzen Zahlen beträgt $S$.
• In jeder Spalte sind die ganzen Zahlen von oben nach unten in aufsteigender Reihenfolge angeordnet.
• Die ganze Zahl in jedem beliebigen Feld ist größer als jede ganze Zahl in jeder Spalte links von diesem Feld.

Unten ist ein Beispiel für eine Bingokarte dargestellt, wenn $N = 5$, $M = 50$ und $S = 685$ gilt.

Für die Feier möchten wir so viele Bingokarten wie möglich herstellen, die die obigen Bedingungen erfüllen. Es dürfen jedoch nicht $2$ oder mehr identische Karten hergestellt werden. Schreibe ein Programm, das den Rest ausgibt, der bei der Division der maximal möglichen Anzahl herstellbarer Bingokarten durch $100000$ entsteht.

Eingabe

Die Eingabe besteht aus $1$ Zeile und enthält $3$ durch Leerzeichen getrennte positive ganze Zahlen, die die Größe der Bingokarte $N$ ($1 \le N \le 7$), die Obergrenze für die in die Felder eingetragenen ganzen Zahlen $M$ ($1 \le M \le 2000$) und die Summe der auf der Bingokarte eingetragenen ganzen Zahlen $S$ ($1 \le S \le 3000$) angeben. Bei allen gegebenen Eingabedaten ist es möglich, mindestens $1$ Bingokarte herzustellen, die die Bedingungen erfüllt.

Ausgabe

Gib in $1$ Zeile den Rest aus, der bei der Division der maximal möglichen Anzahl herstellbarer Bingokarten durch $100000$ entsteht.

Beispiel 1

Eingabe

3 9 45

Ausgabe

1

Beispiel 2

Eingabe

3 100 50

Ausgabe

7

Beispiel 3

Eingabe

5 50 685

Ausgabe

74501

Hinweis

Da für Beispiel $3$ die maximale Anzahl herstellbarer Bingokarten $642499974501$ beträgt, wird $74501$ ausgegeben, was dem Rest bei der Division durch $100000$ entspricht.