Background

Doremi loves traveling.

Problem Description

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.

Input Format

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 Format

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

2 2 2 998244353 1
1 2

7

5 5 0 114514 0

70

5 5 3 998244353 3
3 4
2 5
4 4

13782

Hint

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