Partitioning Pigs into Houses

In order to guarantee their safety, the little pigs have built a new brick house. However, they now face a dilemma on how to allocate the pigs to the houses. Initially, with 3 pigs and 2 houses, the wisest third pig came up with three different allocation schemes, as shown in the image below:

This allocation is done in such a way that no house is left empty. In the example, one house gets a single pig while the other gets the remaining two pigs — and since the pigs are distinguishable but the houses are considered indistinguishable, the only decision is which pig stays alone, yielding exactly 3 schemes.

Now, the pigs foresee that in the future they will have more members and correspondingly build more houses. Given the total number of pigs n and houses k, your task is to compute the number of ways to partition the n pigs into k houses so that every house gets at least one pig.

This number is exactly the Stirling number of the second kind \(S(n,k)\), which satisfies the recurrence:

[ S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k) \quad \text{for } n,k>0, ]

with the base case \(S(0,0)=1\) and \(S(n,0)=0\) for \(n>0\). If \(n < k\), then no valid partition exists, and the answer is 0.

inputFormat

The input consists of a single line with two space-separated integers: n (the number of pigs) and k (the number of houses).

outputFormat

Output a single integer representing the number of allocation schemes (the Stirling number of the second kind \(S(n,k)\)) if \(n \ge k\); otherwise, output 0.

sample

3 2

3