레이팅 미적용While Ivan was working at this year’s chocolate festival, his boss gave him \(n\)
different chocolate candies and asked him to prepare \(k\) chocolate boxes using those
candies. Before he starts arranging the boxes, Ivan wants to find out in how many
different ways he can arrange them, and then, after considering all the possibilities,
he will choose the best arrangement.
The chocolate festival is a very important and serious event, so the candies must be
perfectly arranged. To achieve this, Ivan knows that he must follow the following
rules:
• Each box must contain at least one candy.
• Each candy goes in exactly one box.
• The boxes he uses are identical to each other, so swapping the contents of
two boxes does not create a new arrangement. All that matters is which
candies are in which box and in what order they are arranged.
• The largest candy is always the first in the box. We can assume that in any
group of candies, the largest can always be uniquely determined.
In how many different ways can Ivan arrange the boxes? Since the number of ways can be very large,
print it modulo \(10^{9} + 7\).
The first and only line contains the natural numbers \(n\) and \(k\) (\(1 \le n \le 5000\), \(1 \le k \le n\)), the number of
candies, and the number of boxes.
In the first and only line, print a single number - the number of ways Ivan can arrange the boxes modulo
\(10^{9} + 7\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 8점 | \(k = 1\) |
2 | 19점 | \(k = 2\) |
3 | 14점 | \(n \le 10\) |
4 | 29점 | No additional constraints. |
3 123 234 211Clarification of the first example:
Let’s label the candies from smallest to largest with 1, 2, and 3. We need to arrange them in one box,
so all three candies must be in the same box. Candy 3 must be first because it is the largest. We can
arrange the other two candies in two ways, so [3, 1, 2] and [3, 2, 1] are the only valid arrangements.
Clarification of the second example:
Let’s label the candies from smallest to largest with 1, 2, and 3. We can arrange the candies in three
ways: {[1], [3, 2]}, {[2], [3, 1]}, and {[3], [2, 1]}.