Description

Partition the integer $n$ into $k$ non-empty parts, and regard two partitions as the same if they differ only in order.

For example, when $n=7$, $k=3$, the following three partitions are considered the same: $1, 1, 5$;
$1, 5, 1$;
$5, 1, 1$.

How many different partitions are there?

Input Format

Two integers $n$ and $k$.

Constraints: $6 < n \le 200$, $2 \le k \le 6$.

Output Format

One integer: the number of different partitions.

7 3

4

Hint

There are four partitions when $n=7$, $k=3$:
$1, 1, 5$;
$1, 2, 4$;
$1, 3, 3$;
$2, 2, 3$.

Problem Source: NOIP 2001 Senior, Problem 2.

Translated by ChatGPT 5