F - ビンゴ
解説
/
実行時間制限: 10 sec / メモリ制限: 256 MB
配点: 100 点
問題
あるプログラミングコンテストでは,競技後の懇親会でビンゴゲームをする習わしがある.しかし,このビンゴゲームで使うビンゴカードは少々特殊で,以下の条件に従って作成される.
- ビンゴカードは N 行 N 列のマス目に区切られており,各マス目には正整数が 1 つずつ書かれている.それらの整数は全て異なる.
- マス目に書かれている整数は 1 以上 M 以下である.
- ビンゴカードに書かれている N \times N 個の整数の合計は S である.
- どの列を見たときも,上から下に向かって整数は昇順に並んでいる.
- どのマス目の整数も,そのマス目より左の列のどの整数よりも大きい.
以下は,N = 5,M = 50,S = 685 のときのビンゴカードの例である.
懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい.ただし,同一のカードを 2 枚以上作ってはならない.作ることができるビンゴカードの枚数の最大値を 100\,000 で割った余りを出力するプログラムを作成せよ.
入力
入力は 1 行からなり,その行にはビンゴカードのサイズ N (1 \leqq N \leqq 7),マス目に書かれている整数の上限 M (1 \leqq M \leqq 2\,000),ビンゴカードに書かれている整数の合計 S (1 \leqq S \leqq 3\,000) を表す3つの正整数が空白区切りで書かれている.ただし,与えられるどの入力データにおいても,条件を満たすビンゴカードを 1 枚以上作ることができる.
出力
作ることができるビンゴカードの枚数の最大値を 100\,000 で割った余りを出力せよ.
入力例 1
3 9 45
出力例 1
1
入力例 2
3 100 50
出力例 2
7
入力例 3
5 50 685
出力例 3
74501
入力例 3 に対して,作ることができるビンゴカードの枚数の最大値は 642\,499\,974\,501 であるので,100\,000 で割った余りの 74\,501 を出力する.