题目描述

在某个程序设计竞赛中，按照惯例会在赛后聚会上玩宾果游戏。然而，这个宾果游戏中使用的宾果卡有些特别，是按照以下条件制作的：

• 宾果卡被划分为 $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$。