問題文

あるプログラミングコンテストでは，懇親会でビンゴゲームをする習わしがある．ただし，このビンゴゲームで使うビンゴカードは少々特殊であり，以下の条件に従って作成される．

• ビンゴカードは $N$ 行 $N$ 列のマス目に区切られており，各マス目には正整数が $1$ つずつ書かれている．それらの整数はすべて異なる．
• マス目に書かれている整数は $1$ 以上 $M$ 以下である．
• ビンゴカードに書かれている $N \times N$ 個の整数の合計は $S$ である．
• どの列を見ても，上から下に向かって整数が昇順に並んでいる．
• どのマス目の整数も，そのマスより左の列のどの整数よりも大きい．

以下は，$N = 5$，$M = 50$，$S = 685$ のときのビンゴカードの例である．

懇親会のために，上の条件を満たすビンゴカードをできるだけたくさん作りたい．ただし，同一のカードを $2$ 枚以上作ってはいけない．作ることができるビンゴカードの最大枚数を $100000$ で割った余りを出力するプログラムを作成せよ．

入力

入力は $1$ 行からなり，その行にはビンゴカードのサイズ $N$（$1 \le N \le 7$），マス目に書かれている整数の上限 $M$（$1 \le M \le 2000$），ビンゴカードに書かれている整数の合計 $S$（$1 \le S \le 3000$）を表す $3$ つの正整数が空白区切りで書かれている．ただし，与えられるどの入力データにおいても，条件を満たすビンゴカードを $1$ 枚以上作ることができる．

出力

作ることができるビンゴカードの最大枚数を $100000$ で割った余りを $1$ 行で出力せよ．

入出力例 1

入力

3 9 45

出力

1

入出力例 2

入力

3 100 50

出力

7

入出力例 3

入力

5 50 685

出力

74501

補足

入出力例 $3$ に対して，作ることができるビンゴカードの最大枚数は $642499974501$ 枚であるので，$100000$ で割った余りである $74501$ を出力する．