Description

There are n distinct balls and k identical bins. Write a program to determine how many ways are there to throw the balls into the bins, such that no bin are emtpy.

Take n = 5, k = 3 for example, there are 25 ways in total. One of the way is: [1, 2], [3, 5], [4], where each [ ] denote a bin. Also note that [3, 5], [4], [1, 2] is considered the same way, since the bins are identical.

Input

The first line contains two integer n, k, seperated by a blank.

Constrain

• 1 <= k <= n <= 15.

Output

Output a integer in one line: the number of ways. You need to add '\n' in the end of output.

Hint

Let f(n, k) be the number of ways when there are n balls and k bins. Then we can consider two ways to put the n-th ball:

• Put it into a bin that have no other ball, then the number of ways to put other balls is f(n - 1, k - 1)
• Put it into a bin that have already have other balls (which have k choices of bin), the number of ways ot put other balls is f(n - 1, k)

Hence we have the recurrence f(n, k) = f(n - 1, k - 1) + k * f(n - 1, k), and f(n, k) = 1 when n = k.

You may reference Stirling number of second kind for more details.

Sample Input  Download

Sample Output  Download

Tags

Discuss