Correct Binary Search in a Permutation

We are given a permutation (a) of ({1,2,\ldots,n}) representing a random ordering of numbers. Originally, one expects (a) to be sorted, so the binary search algorithm below would correctly locate an element. However, due to a macro redefinition, the array remains unsorted, i.e. a random permutation. The binary search function is implemented as follows:

[ \begin{aligned} \texttt{int search(int key) { }\ \quad, int\ l = 1,\ r = n;\ \quad, while(l \le r) {\ \quad\quad, int mid = \left\lfloor\frac{l + r}{2}\right\rfloor;\ \quad\quad, if(a[mid] < key)\ \quad\quad\quad, l = mid + 1;\ \quad\quad, else if(a[mid] == key)\ \quad\quad\quad, return mid;\ \quad\quad, else\ \quad\quad\quad, r = mid - 1;\ \quad, }\ \quad, return -1;\ \texttt{}} \end{aligned} ]

In the problem the search is conducted for the (k)-th smallest element in the permutation. Since the sorted order of the permutation is exactly (1,2,\ldots,n), the (k)-th smallest element is (k).

Although the binary search is designed for a sorted array, it might still succeed in locating (k) if certain conditions hold in the random permutation. In particular, if we simulate the binary search with (key=k) over the indices (1) to (n) (pretending that the permutation were sorted, so that position (i) has value (i)), we notice the following:

Define two counters:

[ \begin{aligned} \text{cntLess} &= \text{number of times we choose an index } mid \text{ with } mid < k,\ \text{cntGreater} &= \text{number of times we choose an index } mid \text{ with } mid > k. \end{aligned} ]

The simulation is done by setting (l = 1) and (r = n) and, in each iteration, computing (mid = \lfloor (l+r)/2\rfloor). If (mid < k), then we require that the element in that visited position is less than (k) (it must be chosen from ({1, 2, \ldots, k-1})). Similarly, if (mid > k) the element must be greater than (k) (from ({k+1, k+2, \ldots, n})). Finally, at the moment when (mid = k), we have the candidate where the element must be (k).

Thus, to count the number of valid permutations which make the binary search correctly return an index (i.e. not (-1)), we must have:

[ \text{Answer} = P(k-1,,\text{cntLess}) \times P(n-k,,\text{cntGreater}) \times (n - \text{cntLess} - \text{cntGreater} - 1)! \mod p, ]

where (P(n,r) = n \times (n-1) \times \cdots \times (n-r+1)) is the permutation function.

Your task is to compute the number of valid permutations modulo (p) given the values (n), (k), and (p).

inputFormat

The input consists of a single line containing three integers (n), (k), and (p) separated by spaces.

Constraints (for example):

• (1 \le k \le n \le 10^5)
• (1 \le p \le 10^9+7)

outputFormat

Output a single integer: the number of valid permutations modulo (p).

sample

5 2 1000000007

6