问题

在某个编程竞赛中，比赛后会举办联谊会，其中有一个传统的游戏叫做Bingo。但是，这个Bingo游戏使用的Bingo卡有些特殊，根据以下条件创建：

• Bingo卡被划分为N行N列的格子，每个格子上都写着一个正整数。这些整数都是不同的。
• 写在格子中的整数的范围是从1到M。
• Bingo卡上的N×N个整数的和为S。
• 无论从哪一列看，整数都是按照从上到下的升序排列的。
• 任意一个格子中的整数都要大于其左边列的任意一个整数。

下面是当N=5，M=50，S=685时的一个Bingo卡的例子：

为了联谊会，我们想尽可能多地制作出满足上述条件的Bingo卡。但是，不能制作两张或两张以上相同的卡。请编写一个程序来计算能够制作的Bingo卡的最大数量，然后将该最大值除以100,000的余数输出。

输入

输入只有一行，该行包含三个正整数，分别表示Bingo卡的大小N（1 ≤ N ≤ 7），格子上整数的上限M（1 ≤ M ≤ 2,000）和Bingo卡上整数的总和S（1 ≤ S ≤ 3,000）。在给定的任何输入数据中，都可以制作一个满足条件的Bingo卡。

输出

请输出能够制作的Bingo卡的最大数量除以100,000的余数。

输入示例1

3 9 45

输出示例1

1

输入示例2

3 100 50

输出示例2

7

输入示例3

5 50 685

输出示例3

74501

对于输入示例3，能够制作的Bingo卡的最大数量是642,499,974,501，所以输出结果为74,501除以100,000的余数。