Description

First, let us recall the classic difficult problem, River-Crossing Pawn:

On a chessboard, there is a river-crossing pawn at point $A$ that needs to move to the target point $B$. The pawn moves by the following rules: it can move up, or move right. Meanwhile, there is an opponent knight at point $C$. The knight’s position and all positions it can reach by one knight move are called the opponent knight’s controlled points, hence the name “the knight blocks the river-crossing pawn”.

The chessboard is represented by coordinates: $A$ is $(1,1)$, $B$ is $(N,M)$, and the knight’s coordinate is also given.

Now you are asked to compute the number of paths for the pawn to get from $A$ to $B$, assuming the knight stays fixed and does not move after each pawn move.

Note that the background above is unrelated to this problem!

Kiana likes playing Chinese chess, and she especially likes using Chinese chess pieces to play the river-crossing pawn game. In the traditional river-crossing pawn problem, Kiana needs to control a pawn to move from the start to the end, avoiding the attacks of an opponent knight on the way, and then pretends she cannot calculate it and asks you for the total number of paths from the start to the end.

In today’s River-Crossing Pawn II game, Kiana still controls a pawn moving on an $N\times M$ board. Initially, the pawn is at the bottom-left position with coordinate $(1,1)$. To make the game harder, Kiana changes some rules. In the traditional version, the pawn can only move up or right by $1$ cell each step. Kiana allows her River-Crossing Pawn II to also move up-right by $1$ cell in one step. That is, if the pawn is currently at $(x,y)$, then the next step can go to any of $(x+1,y)$, $(x,y+1)$, or $(x+1,y+1)$. Kiana also considers that if two movement plans differ in the moving direction (right, up, or up-right) at any step, then they are different plans. For example, from $(1,1)$ to $(1,2)$ then to $(2,2)$, from $(1,1)$ to $(2,1)$ then to $(2,2)$, and from $(1,1)$ directly to $(2,2)$ are three different movement plans.

Second, the goal of River-Crossing Pawn II is no longer a specific position. Kiana defines that the pawn may leave the board from the top side or the right side, and then the game is considered successful. Note that when leaving the board, there are still different direction choices. For example, if the pawn is at $(1,M)$, then in the next step it can leave the board in two ways: right or up-right. If the pawn is at $(N,M)$, then in the next step it can leave the board in three ways: up, right, or up-right. Leaving the board in different ways is still counted as different movement plans.

In addition, the opponent knight’s attack range is no longer a few regular positions. Instead, Kiana specifies $K$ particular coordinates, and the pawn is not allowed to step on any of these $K$ coordinates during its movement. On all other positions, the pawn may move freely according to the rules.

Now Kiana wants to know how many different movement plans allow the pawn to leave the board. The answer can be very large; she only wants the result modulo $59393$. Since she cannot compute it, she asks you to tell her.

Input Format

The first line contains three integers $N$, $M$, and $K$, representing the coordinate ranges of the board and the number of squares attacked by the opponent knight (i.e., the number of coordinates that Kiana specifies as forbidden).

The next $K$ lines each contain two positive integers $X_i$ and $Y_i$, meaning the $i$-th attacked coordinate is $(X_i,Y_i)$.

For all data, it is guaranteed that $1\leq N\leq 10^9$, $1\leq M\leq 10^5$, $0\leq K\leq 20$, $1\leq X_i\leq N$, $1\leq Y_i\leq M$. The cell $(1,1)$ is definitely not attacked by the opponent knight, and among the attacked cells there are no two cells with the same coordinate.

Output Format

Output one line with one integer, the number of movement plans for the pawn to leave the board modulo $59393$.

3 3 1
2 2

24

Hint

Sample Explanation

Use $\uparrow$ to represent that the pawn moves up by one cell, use $\rightarrow$ to represent that the pawn moves right by one cell, and use $\nearrow$ to represent that the pawn moves up-right by one cell. This can simplify the description of the sample explanation.

The $24$ movement plans are:

$(\uparrow\uparrow\uparrow)$、$(\uparrow\uparrow\nearrow)$、$(\uparrow\uparrow\rightarrow\uparrow)$、$(\uparrow\uparrow\rightarrow\nearrow)$、

$(\uparrow\uparrow\rightarrow\rightarrow\uparrow)$、$(\uparrow\uparrow\rightarrow\rightarrow\nearrow)$、$(\uparrow\uparrow\rightarrow\rightarrow\rightarrow)$、$(\uparrow\nearrow\uparrow)$、

$(\uparrow\nearrow\nearrow)$、$(\uparrow\nearrow\rightarrow\uparrow)$、$(\uparrow\nearrow\rightarrow\nearrow)$、$(\uparrow\nearrow\rightarrow\rightarrow)$、

$(\rightarrow\rightarrow\rightarrow)$、$(\rightarrow\rightarrow\nearrow)$、$(\rightarrow\rightarrow\uparrow\rightarrow)$、$(\rightarrow\rightarrow\uparrow\nearrow)$、

$(\rightarrow\rightarrow\uparrow\uparrow\rightarrow)$、$(\rightarrow\rightarrow\uparrow\uparrow\nearrow)$、$(\rightarrow\rightarrow\uparrow\uparrow\uparrow)$、$(\rightarrow\nearrow\rightarrow)$、

$(\rightarrow\nearrow\nearrow)$、$(\rightarrow\nearrow\uparrow\rightarrow)$、$(\rightarrow\nearrow\uparrow\nearrow)$、$(\rightarrow\nearrow\uparrow\uparrow)$。

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as editorial solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5