題目描述

喺某個程式設計比賽入面，按照慣例會喺賽後派對度玩賓果遊戲（Bingo）。不過，呢個賓果遊戲入面用嘅賓果卡有啲特別，係按照以下條件製作嘅：

• 賓果卡被劃分成 $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$ 張賓果卡，所以輸出佢除以 $100000$ 嘅餘數 $74501$。