Seating Arrangement with Fixed Numbers

You are given n persons numbered from 1 to n. Each person i is associated with an integer a_i (which can be any number from 1 to n and may repeat). The seating procedure is as follows: starting from person 1 and proceeding to person n, when person i arrives they attempt to sit in seat number a_i. If seat a_i is already occupied, they try seat a_i+1, then a_i+2, and so on. If they reach seat n and still cannot find an empty seat, the arrangement is considered illegal.

In addition, the numbers for m persons have already been fixed (for example, due to extraneous influence). You are allowed to freely choose the numbers for the remaining n-m persons (each choice must be an integer between 1 and n).

A key observation is that a complete assignment (fixed and chosen numbers) yields a legal seating arrangement if and only if the sorted sequence of all a_i satisfies \[ b_1 \le 1,\; b_2 \le 2,\; \dots ,\; b_n \le n,\] which is the well‐known parking function condition.

Your task is to count the number of valid assignments for the free persons such that, when combined with the fixed numbers, the overall sequence is a parking function. Since the answer may be very large, output the result modulo M.

Input/Output Formats: See below.

inputFormat

The first line contains three integers: n (1 ≤ n), m (0 ≤ m ≤ n), and M (the modulus).

The next m lines each contain one integer representing the fixed number for a particular person. Each fixed number is between 1 and n (inclusive). Persons without a fixed number can be assigned any integer between 1 and n.

outputFormat

Output a single integer – the number of valid complete assignments modulo M.

sample

3 1 100
1

8