Bingo

Time Limit : 1 sec, Memory Limit : 65536 KB

ビンゴ

問題

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

  • ビンゴカードは N 行 N 列のマス目に区切られており,各マス目には正整数が1つずつ書かれている.それらの整数は全て異なる.
  • マス目に書かれている整数は 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 で割った余りを出力せよ.

入出力の例

入力例1 入力例2 入力例3
3 9 45
3 100 50
5 50 685
 
出力例1 出力例2 出力例3
1
7
74501

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

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. N, M, S が 0 のとき入力の終わりを示します.

Sample Input

3 9 45
3 100 50
0 0 0

Sample Output

1
7

Source: 8th Japanese Olympiad in Informatics, Preliminary Round , 2008-12-14
http://www.ioi-jp.org/