題目描述

在某個程式設計競賽中，按照慣例會在賽後派對上玩賓果遊戲。然而，這個賓果遊戲中使用的賓果卡有些特別，是按照以下條件製作的：

• 賓果卡被劃分為 $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$。