P3904 The Three Little Pigs

Have you heard the story of the Three Little Pigs? It is a classic tale. Long, long ago, there were three little pigs. The first little pig built a house of straw, the second little pig built a house of sticks, and the third little pig used bricks as the material. A big bad wolf wanted to eat them and blew down the straw house and the stick house. But the brick house was very sturdy, and the wolf failed to destroy it. In the end, the little pigs defeated the wolf and burned its tail.

For their safety, the little pigs built another new brick house. But now a problem arises: how should the three little pigs be assigned to the two houses? The third little pig is the smartest of the three. To avoid wasting any house, it considered a total of three plans, as shown below.  "But what about the future?" The third little pig knows that as their group grows, they will build more houses. It wants to know, given the numbers of houses and pigs, how many allocation plans there are. However, this problem is clearly a bit hard for it. Can you help the little pig solve it?

The input contains a single line with two integers $n$ and $m$, denoting the number of pigs and the number of houses ($1 \leq n, m \leq 50$).

Output a single integer: the number of ways to place $n$ pigs into $m$ houses such that no house is left empty.

Translated by ChatGPT 5