問題

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

• ビンゴカードは $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$) を表す3つの正整数が空白区切りで書かれている．ただし，与えられるどの入力データにおいても，条件を満たすビンゴカードを $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$ を出力する．