Crossing Pawn II

Kiana loves playing Chinese chess, especially when using the pawn (卒) in the classic "Crossing Pawn" puzzle. In the traditional problem, a pawn starts at a fixed position and must avoid enemy pieces to reach a specific target. However, in Crossing Pawn II, Kiana has modified the rules to add extra challenge.

The game is played on an \(N \times M\) board. The pawn starts at the bottom‑left cell with coordinates \((1,1)\). In each move, the pawn may advance by one cell in one of three directions:

• Right: from \((x,y)\) to \((x+1,y)\).
• Up: from \((x,y)\) to \((x,y+1)\).
• Diagonally up‑right: from \((x,y)\) to \((x+1,y+1)\).

Unlike the traditional version, two moves that use different directions are considered distinct even if they lead to the same cell. For example, going from \((1,1)\) to \((2,2)\) can be done in three different ways:

• Diagonal move directly from \((1,1)\) to \((2,2)\).
• Right then up: from \((1,1)\) to \((2,1)\) and then \((2,1)\) to \((2,2)\).
• Up then right: from \((1,1)\) to \((1,2)\) and then \((1,2)\) to \((2,2)\).

The ending condition is also different. Instead of reaching a fixed terminal cell, the pawn succeeds by stepping off the board from either the top or the right boundary. Note that when leaving the board, the direction of the final move still matters. For instance, if the pawn is at \((1,M)\) (on the top edge but not necessarily at the right corner), it may depart by moving right or diagonally up‑right, and these are counted as two distinct exits. Similarly, a pawn at \((N,M)\) (the top‑right corner) has three distinct exit moves: up, right, or diagonally up‑right.

Furthermore, there are \(K\) forbidden cells on the board at fixed positions. The pawn is not allowed to land on any of these forbidden cells during its journey. All other cells are safe.

Your task is to compute the number of distinct ways for the pawn to successfully exit the board, modulo \(59393\). The pawn always moves according to the rules above, and the forbidden cells must be strictly avoided.

Note: The background story is only for fun and does not affect the problem conditions.

inputFormat

The first line of input contains three integers \(N\), \(M\), and \(K\), where \(N\) and \(M\) represent the dimensions of the board and \(K\) is the number of forbidden cells.

Each of the next \(K\) lines contains two integers \(x\) and \(y\), indicating that the cell at \((x, y)\) is forbidden. The pawn starts at \((1,1)\), and it is guaranteed that \((1,1)\) is not forbidden.

outputFormat

Output a single integer: the number of distinct ways the pawn can exit the board (from the top or right boundaries) modulo \(59393\).

sample

2 2 0

13