問題

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

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

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

懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい．ただし，同一のカードを 2 枚以上作ってはならない．作ることができるビンゴカードの枚数の最大値を 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 を出力する．