Count Cherry Tree Planting Arrangements

Fusu loves listening to ancient tunes while solving mathematical problems. In this problem, he wishes to recreate the beautiful scene of cherry blossoms in full bloom on the Qingyuan slope. He has prepared many distinct cherry tree saplings and plans to plant them in a row of n available positions. However, because a blooming cherry tree requires ample space on both sides, no two saplings can be planted adjacently; that is, there must be at least one empty position between any two planted saplings.

If Fusu has prepared m saplings (which are labelled 1, 2, 3, ..., m) and he plants them in a valid way, then two arrangements are considered different if either the set of chosen positions is different or the sequence of labels from left to right is different.

Your task is to count the number of valid arrangements in which all m saplings can be planted, and output the count modulo \(p\). A valid arrangement exists if and only if between every two saplings there is at least one empty position. Note that if it is impossible to plant all saplings under the given constraint then the answer is 0.

Hint: One way to count the arrangements is to first choose m positions out of the available positions so that any two chosen positions have a gap of at least 1. This selection can be shown to be equivalent to choosing m positions from \(n-m+1\) positions. After selecting the positions, the m distinct saplings can be arranged in those positions in \(m!\) ways. Therefore, the total number of ways is:

[ \text{Answer} = m! \times \binom{n-m+1}{m} \mod p. ]

inputFormat

The input consists of a single line containing three space-separated integers:

• n: the number of positions available for planting.
• m: the number of cherry tree saplings.
• p: the modulus.

You may assume that the input parameters are such that \(0 \le m \le n\) and \(p \ge 1\).

outputFormat

Output a single integer representing the number of valid arrangements to plant all the saplings modulo p.

sample

5 2 100

12