Counting Valid Parking Function Extensions

Given (n) people arriving sequentially (numbered from (1) to (n)), each person is assigned an integer in ([1, n]) as his/her initial seat preference. Let the (i)th person’s preference be (a_i) (note that different people may receive the same number). They enter in order: when the (i)th person arrives, he/she first tries to sit at seat (a_i). If that seat is already occupied, the person then tries (a_{i+1}), then (a_{i+2}), and so on up to seat (n). If none of the seats from (a_i) to (n) is free, the seating arrangement is considered illegal.

Furthermore, the preferences for (m) persons are fixed (perhaps due to some behind‐the‐scenes influence) and cannot be changed. You are allowed to assign the preferences for the remaining (n-m) persons arbitrarily (each integer from (1) to (n) is allowed). Your task is to count the number of ways to assign preferences for the unfixed persons so that the entire assignment (a_1,a_2,\dots,a_n) is legal. A necessary and sufficient condition for legality is that the resulting sequence is a parking function; that is, when the (n) numbers are sorted into non–decreasing order (b_1 \le b_2 \le \cdots \le b_n), we must have [ b_i \le i, \quad \text{for all } 1\le i\le n. ] This is equivalent to the condition that for every (j) with (1\le j\le n), if (F(j)) is the number of fixed persons with preference (\le j) and (X(j)) is the number of unfixed persons (whose preferences you assign) with preference (\le j), then we must have [ F(j) + X(j) \ge j. ] Output the number of legal completion schemes modulo (M).

Input Format: The first line contains three integers (n, m, M). Each of the next (m) lines contains two integers (pos) and (v), indicating that the person in position (pos) (1–indexed) has a fixed preference of (v) (where (1\le v\le n)). It is guaranteed that all fixed positions are distinct.

Note: You must assign the unfixed persons a value in ([1,n]) arbitrarily, and then the complete sequence (a_1, a_2, \dots, a_n) must satisfy the above parking function condition.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(M\). Then \(m\) lines follow, each containing two integers \(pos\) and \(v\) separated by a space, indicating that the person at position \(pos\) has a fixed preference of \(v\).

Constraints (for this problem instance):
1 \(\le n \le\) 10, and 0 \(\le m \le n\).
1 \(\le v \le n\).
1 \(\le M \le 10^9\).

outputFormat

Output a single integer: the number of valid ways to assign preferences to the unfixed persons, modulo \(M\).

sample

3 1 1000
2 1

8