Distribution of Distinct Balls into Identical Boxes

Given N distinct balls and M identical boxes, where each box must contain at least one ball, determine the number of ways to distribute the balls among the boxes.

This problem is equivalent to finding the number of ways to partition a set of N elements into M non-empty subsets, i.e., the Stirling numbers of the second kind \( S(N, M) \).

The recurrence relation for the Stirling numbers of the second kind is:

\[ S(n, m) = m \times S(n-1, m) + S(n-1, m-1), \quad \text{with} \quad S(n,n)=1 \quad \text{and} \quad S(n,1)=1. \]

Your task is to compute \( S(N, M) \) given the integers N and M.

inputFormat

The input consists of a single line containing two integers N and M separated by a space.

Constraints: You can assume that N and M are such that the answer can be computed using dynamic programming without overflow issues.

outputFormat

Output a single integer which is the number of ways to distribute N distinct balls into M identical boxes with each box containing at least one ball.

sample

3 2

3