2008年12月14日
情報オリンピック日本委員会
問題
あるプログラミングコンテストでは，
競技後の懇親会でビンゴゲームをする習わしがある．
しかし，
このビンゴゲームで使うビンゴカードは少々特殊で，
以下の条件に従って作成される．
-
ビンゴカードは 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 を出力する．
※各入出力例のデータは，
右クリック等によりファイルに保存して利用可能です．
テストデータ
