ビンゴ

問題

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

• ビンゴカードは 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枚以上作ることができる．

N, M, S が 0 のとき入力の終了を示す. データセットの数は 5 を超えない．

出力

データセットごとに, 作ることができるビンゴカードの枚数の最大値を 100000 で割った余りを1行に出力せよ．

入出力例

入力例

3 9 45
3 100 50
5 50 685
0 0 0

出力例

1
7
74501

3つ目の入力例に対して，作ることができるビンゴカードの枚数の最大値は 642499974501 であるので， 100000 で割った余りの 74501 を出力する．