Counting Surjections: Assign Balls to Boxes

Given r distinct boxes and n distinct balls, distribute the n balls into the r boxes such that no box is empty. Two distributions are considered different if and only if there exists at least one ball that is placed in different boxes between the two distributions.

The total number of valid distributions is equal to the number of surjective functions from an n-element set to an r-element set. This can be expressed by the formula:

$$ \sum_{k=0}^{r}(-1)^k\binom{r}{k}(r-k)^n $$

Alternatively, it can be written as:

$$r!\,S(n, r)$$

where \(S(n,r)\) denotes the Stirling numbers of the second kind.

inputFormat

The input consists of two integers n and r (with 1 ≤ r ≤ n ≤ 20) separated by a space.

outputFormat

Output a single integer representing the number of valid distributions.

sample

3 2

6