You are given $n$ distinct candies labeled from $1$ to n and $k$ identical bags.

You need to distribute all n candies into the k bags such that each bag contains at least $1$ candy.

Return the total number of ways to distribute the candies. Since the answer may be large, return it modulo $10^9 + 7$.

Note: Bags are identical, so the order of the bags does not matter. Two distributions are considered different if there exist two candies that are in the same bag in one distribution but in different bags in the other distribution.

Constraints:

• $1 \leq$ k $\leq$ n $\leq 1000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.