ビンゴ

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

ビンゴカードは N 行 N 列のマス目に区切られており,
各マス目には正整数が1つずつ書かれている.
それらの整数は全て異なる.

マス目に書かれている整数は 1 以上 M 以下である.

ビンゴカードに書かれている\(N \times N\)個の整数の合計は S である.

どの列を見たときも,
上から下に向かって整数は昇順に並んでいる.

どのマス目の整数も,
そのマス目より左の列のどの整数よりも大きい.

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

懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい.
ただし,
同一のカードを2枚以上作ってはならない.
作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを出力するプログラムを作成せよ.

入力は1行からなり,
その行にはビンゴカードのサイズ N (\(1 \le N \le 7\)) ,
マス目に書かれている整数の上限 M (\(1 \le M \le 2000\)) ,
ビンゴカードに書かれている整数の合計 S (\(1 \le S \le 3000\)) を表す3つの正整数が空白区切りで書かれている.
ただし,
与えられるどの入力データにおいても,
条件を満たすビンゴカードを1枚以上作ることができる.

作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2009 Preliminary