P10027 Dream World.

Doremi loves traveling.

There is a grid of length $n$ and width $m$. Its top-left corner is position $(1, 1)$, and its bottom-right corner is position $(n, m)$. Doremi wants to walk from the top-left corner to the bottom-right corner. Each time, she can move one cell to the right or one cell downward, but she cannot go out of the $n \times m$ grid boundary. Besides, there are $s$ forbidden cells that Doremi cannot step on. Doremi has $k$ magic potions. Drinking a potion can undo the last not-yet-undone walking move, but the move sequence will not delete its last element. Of course, she cannot use a potion at position $(1, 1)$, and **a potion will not undo the effect of the previous potion**. For example, after moving from $A$ to $B$, if she drinks a potion at $B$, then the move sequence is $A \to B \to A$. If she walks from $A$ to $B$ and then to $C$, and drinks two potions consecutively, then the move sequence is $A \to B \to C \to B \to A$. Doremi considers a **trip** to be a walking route that finally reaches $(n, m)$. She wants to find the number of essentially different **trips**, modulo the given $p$. She considers two **trips** to be different if and only if the recorded move sequences are different.

The first line contains five integers $n, m, k, p, s$, with meanings as described above. The next $s$ lines each contain two integers $(x_i, y_i)$, meaning that the cell labeled $(x_i, y_i)$ in the grid cannot be passed through.

Output one integer in one line, representing the answer modulo $p$.

### Sample Explanation 1 The seven routes are as follows:  ### Constraints **This problem uses bundled tests.** - Subtask 0 (10 pts): $1 \le n, m \le 100$, $k = 0$. - Subtask 1 (15 pts): $1 \le n, m \le 10$, $k = 1$. - Subtask 2 (15 pts): $n = 1$, $m \le 100$, $k \le 100$. - Subtask 3 (25 pts): $1 \le n, m \le 100$, $k \le 10$. - Subtask 4 (35 pts): No special restrictions. For all testdata, it is guaranteed that $1 \le n, m \le 100$, $0 \le k \le 100$, $2 \le p \le 10^9 + 9$, $0 \le s \le n \times m$, $1 \le x_i \le n$, $1 \le y_i \le m$, and all $(x_i, y_i)$ are distinct. Translated by ChatGPT 5