Description

In the same orchard where Tao Tao picked apples, Long Xiong picked $n$ completely distinct apples. The hospitable owner provided him with $k$ baskets. He wants to put the apples into the baskets and carry them home (since Long Xiong’s hands are infinitely large, you do not need to consider whether he can carry multiple baskets at once).

He also does not want any basket to be empty, so as to make full use of the baskets. Therefore, he wants to know how many ways there are to distribute the apples. Because his brain computes slowly, he has asked you for help. He has already spent a long time picking apples, so he can only wait $1$ second.

Since the number of ways may be extremely large, he will give you a number $p$; output the remainder when the number of ways is divided by $p$.

Two distributions are considered the same if each basket contains the same set of apples, and the order of baskets does not matter.

Input Format

One line with three integers $n$, $k$, and $p$, as described above.

Output Format

A single integer: the remainder when the number of ways is divided by $p$, followed by a newline.

4 2 3

1

Hint

Sample explanation:

There are $4$ apples and $2$ baskets.

There are the following $7$ ways.

• $\{1\},\{2,3,4\}$.
• $\{2\},\{1,3,4\}$.
• $\{3\},\{1,2,4\}$.
• $\{4\},\{1,2,3\}$.
• $\{1,2\},\{3,4\}$.
• $\{1,3\},\{2,4\}$.
• $\{1,4\},\{2,3\}$.

$7$ divided by $3$ leaves a remainder of $1$.

Constraints:

• For $20\%$ of the testdata, $n \le 8$, $k \le 8$.
• For $60\%$ of the testdata, $n \le 100$, $k \le 100$.
• For $100\%$ of the testdata, $n \le 10000$, $k \le 1000$.

It is guaranteed for all testdata that $n \ge k$, and the answer fits in a $64$-bit integer.

Translated by ChatGPT 5