配点: 100 点
問題
在某些编程比赛中,比赛结束后的聚会习惯玩宾果游戏。然而,用于宾果游戏的宾果卡稍有特殊,根据以下条件制作。
- 宾果卡片是 N 行 N 按列划分的方格,每个方格中写有正整数 1 个。这些整数全部不同。
- 方格中写的整数是 1 以上 M 不超过。
- 宾果卡片上写的 N \times N 个整数的总数是 S 是。
- 无论看哪一列,从上到下整数都是按升序排列的。
- 任意格子的整数都大于该格子左边列的任意整数。
以下是,N = 5,M = 50,S = 685 时的宾果卡示例。

为了联欢会,希望尽可能多地制作满足上述条件的宾果卡。但是,同一张卡不能制作 2 张以上。能够制作的宾果卡最大数量是 100\,000 的余数。
入力
输入是 1 与宾果卡的尺寸一致。 N (1 \leqq N \leqq 7), 方格中写入的整数上限 M (1 \leqq M \leqq 2\,000), 宾果卡上写入的整数总数 表示 S (1 \leqq S \leqq 3\,000的三个正整数以空格分隔。然而,给定任何输入数据,我们都可以找到一张满足条件的宾果卡。 您可以赚取超过 1 的钱。
出力
可以制作的宾果卡最大数量为 打印除以 100\,000 后的余数。 对于
入力例 1
3 9 45
出力例 1
1
入力例 2
3 100 50
出力例 2
7
入力例 3
5 50 685
出力例 3
74501
入力例 3 ,可以制作的宾果卡的最大数量为 642\,499\,974\,501 ,所以 除以100\,000 后的余数 输出 74\,501 。