|
問題
あるプログラミングコンテストでは， 競技後の懇親会でビンゴゲームをする習わしがある． しかし， このビンゴゲームで使うビンゴカードは少々特殊で， 以下の条件に従って作成される．
- ビンゴカードは N 行 N 列のマス目に区切られており， 各マス目には正整数が１つずつ書かれている． それらの整数は全て異なる．
- マス目に書かれている整数は 1 以上 M 以下である．
- ビンゴカードに書かれているN×N個の整数の合計は S である．
- どの列を見たときも， 上から下に向かって整数は昇順に並んでいる．
- どのマス目の整数も， そのマス目より左の列のどの整数よりも大きい．
以下は， N = 5, M = 50, S = 685 のときのビンゴカードの例である．
懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい． ただし， 同一のカードを2枚以上作ってはならない． 作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを出力するプログラムを作成せよ．
入力
入力は1行からなり， その行にはビンゴカードのサイズ N (1≦N≦7) ， マス目に書かれている整数の上限 M (1≦M≦2000) ， ビンゴカードに書かれている整数の合計 S (1≦S≦3000) を表す3つの正整数が空白区切りで書かれている． ただし， 与えられるどの入力データにおいても， 条件を満たすビンゴカードを1枚以上作ることができる．
出力
作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを出力せよ．
入出力例
| 入力例１ | 入力例２ | 入力例３ |
|---|---|---|
|
|
|
| 出力例１ | 出力例２ | 出力例３ |
|
|
|
入力例3に対して， 作ることができるビンゴカードの枚数の最大値は 642499974501 であるので， 100000 で割った余りの 74501 を出力する．
※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．