25837번 - Boring Solitaire 다국어

문제

During quarantine, Stacking-Knightro (SK) made a new card game. SK respects social distancing and, since SK didn’t have other people around, the game is a type of solitaire. SK will shuffle a deck of cards. Then, at every step, SK takes the card at the top of the deck. When taking the card, SK will place the card on top of one of the existing piles of cards or will make a new pile with this card as the top. SK can only place a card on top of a pile if the value of the card is not less than the card at the top of the pile. The goal of the game is to minimize the number of piles when the deck is empty.

Stacking-Knightro started getting pretty good “score” before too long, so the game became pretty boring once SK figured out the “trick”. SK wants to know how many different starting card arrangements will end up with at most K piles if the game is played optimally at each step, i.e., each card is placed such that it will result in the best outcome.

We have a deck of cards with values 1 through V and a number of suits S, i.e., there are “(V × S)!” arrangements of the cards in the deck (note that “!” refers to the factorial of an integer). Using the game description above and a desired maximum of K piles, you are to determine how many different starting card orders will end up with at most K piles. Since this value can be large, print the output mod 1,000,000,007.

입력

There is only one input line; it contains three integers: V (1 ≤ V ≤ 100), representing the number of card values (values are 1 through V), S (1 ≤ S ≤ 10,000), representing the number of suits, and K (1 ≤ K ≤ V ≤ 100), representing the maximum number of piles allowed.

출력

Print how many different starting card orders will end up with at most K piles.

제한

힌트

Explanation of the first Sample Input/Output:

There are two card values, two suites, and one pile. There are four card arrangements to win the solitaire:

1. 1_s1 1_s2 2_s1 2_s2
2. 1_s1 1_s2 2_s2 2_s1
3. 1_s2 1_s1 2_s1 2_s2
4. 1_s2 1_s1 2_s2 2_s1