Problem Background

Doremi loves traveling.

Problem Description

There is a grid of size $n$ by $m$, with the top-left corner numbered as position $(1, 1)$ and the bottom-right corner numbered as position $(n, m)$. Doremi wants to travel from the top-left corner to the bottom-right corner. Each step, she can move one cell to the right or one cell down, but she cannot move outside the boundaries of the $n \times m$ grid. Additionally, there are $s$ forbidden points that Doremi cannot pass through.

Doremi has $k$ magical potions. Drinking a potion can undo the last non-canceled move, but the sequence of moves does not remove the last element. Of course, she cannot use a potion at the starting position $(1, 1)$, and a potion does not undo the previous potion's action. For example: After moving from $A$ to $B$, if she drinks a potion at $B$, the sequence of moves is $A \to B \to A$; if she moves from $A$ to $B$ to $C$ and drinks two potions consecutively, the sequence of moves is $A \to B \to C \to B \to A$.

Doremi defines a journey as a path that ultimately reaches $(n, m)$. She wants to find the number of distinct journeys, modulo a given number $p$. Doremi considers two journeys different if and only if the recorded sequences of moves are different.

Input Format

The first line contains five integers $n, m, k, p, s$, as described in the problem statement.

The next $s$ lines each contain two integers $(x_i, y_i)$, indicating that the point numbered $(x_i, y_i)$ in the grid is forbidden.

Output Format

Output a single integer, which is the answer modulo $p$.

Sample Input and Output

Sample Input #1

2 2 2 998244353 1
1 2

Sample Output #1

7

Sample Input #2

5 5 0 114514 0

Sample Output #2

70

Sample Input #3

5 5 3 998244353 3
3 4
2 5
4 4

Sample Output #3

13782

Notes

Sample Explanation 1

The seven routes are as follows:

Data Size and Constraints

This problem uses subtask testing.

• Subtask 0 (10pts): $1 \le n, m \le 100$, $k=0$.
• Subtask 1 (15pts): $1 \le n, m \le 10$, $k=1$.
• Subtask 2 (15pts): $n=1$, $m \le 100$, $k \le 100$.
• Subtask 3 (25pts): $1 \le n, m \le 100$, $k \le 10$.
• Subtask 4 (35pts): No additional constraints.

For all data, 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 $(x_i, y_i)$ are distinct.

见题面 Input 部分

见题面 Output 部分