1346. Count Ways to Distribute Candies

You have n distinct candies labelled 1 through n and k identical bags. Return the number of ways to distribute all candies so that every bag is non-empty, modulo 1000000007. Bags are indistinguishable, so two distributions differing only by relabelling the bags are the same.

Input: A JSON object {"n": <candy count>, "k": <bag count>}.

Output: Return the number of distributions modulo 1000000007.

Examples

Input: {"n":3,"k":2}
Output: 3
Explanation: Three ways to split three candies into two non-empty identical bags.

Input: {"n":4,"k":2}
Output: 7
Explanation: Seven ways for four candies into two bags.

Constraints

• 1 <= k <= n <= 1000

Asked by