Deskripsi Masalah
Pada suatu kontes pemrograman, terdapat kebiasaan untuk bermain permainan bingo di pesta ramah tamah setelah kontes. Akan tetapi, kartu bingo yang digunakan dalam permainan bingo ini agak khusus dan dibuat berdasarkan ketentuan berikut:
- Sebuah kartu bingo dibagi menjadi kisi-kisi berukuran $N$ baris dan $N$ kolom, dan pada setiap petak tertulis $1$ bilangan bulat positif. Semua bilangan bulat tersebut berbeda satu sama lain.
- Bilangan bulat yang tertulis pada setiap petak bernilai paling sedikit $1$ dan paling banyak $M$.
- Jumlah dari $N \times N$ bilangan bulat yang tertulis pada kartu bingo adalah $S$.
- Jika dilihat pada kolom mana pun, bilangan-bilangan bulatnya tersusun dalam urutan menaik dari atas ke bawah.
- Bilangan bulat pada petak mana pun lebih besar daripada bilangan bulat mana pun yang berada di kolom sebelah kiri petak tersebut.
Di bawah ini adalah contoh kartu bingo ketika $N = 5$, $M = 50$, dan $S = 685$.
Untuk pesta tersebut, kita ingin membuat sebanyak mungkin kartu bingo yang memenuhi ketentuan di atas. Namun, kita tidak boleh membuat $2$ atau lebih kartu yang identik. Buatlah program untuk mengeluarkan sisa pembagian ketika banyaknya kartu bingo maksimum yang dapat dibuat dibagi dengan $100000$.
Masukan
Masukan terdiri dari $1$ baris yang berisi $3$ bilangan bulat positif yang dipisahkan oleh spasi, masing-masing menyatakan ukuran kartu bingo $N$ ($1 \le N \le 7$), batas atas bilangan bulat yang tertulis pada petak $M$ ($1 \le M \le 2000$), dan jumlah bilangan bulat yang tertulis pada kartu bingo $S$ ($1 \le S \le 3000$). Pada semua data masukan yang diberikan, dapat dibuat paling sedikit $1$ kartu bingo yang memenuhi ketentuan.
Keluaran
Keluarkan dalam $1$ baris sisa pembagian ketika banyaknya kartu bingo maksimum yang dapat dibuat dibagi dengan $100000$.
Contoh 1
Masukan
3 9 45
Keluaran
1
Contoh 2
Masukan
3 100 50
Keluaran
7
Contoh 3
Masukan
5 50 685
Keluaran
74501
Catatan
Untuk Contoh $3$, karena banyaknya kartu bingo maksimum yang dapat dibuat adalah $642499974501$, keluarkan $74501$, yaitu sisa pembagian ketika dibagi dengan $100000$.