AT_joi2009yo_f ビンゴ

[problemUrl]: https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_f あるプログラミングコンテストでは，競技後の懇親会でビンゴゲームをする習わしがある．しかし，このビンゴゲームで使うビンゴカードは少々特殊で，以下の条件に従って作成される． - ビンゴカードは $ 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 $ で割った余りを出力せよ． - - - - - -

### Sample Explanation 1 \- - - - - - ### Sample Explanation 2 \- - - - - - ### Sample Explanation 3 入力例 $ 3 $ に対して，作ることができるビンゴカードの枚数の最大値は $ 642\,499\,974\,501 $ であるので，$ 100\,000 $ で割った余りの $ 74\,501 $ を出力する．