19123번 - Master Zhu and the Leaper 다국어

Consider an $n \times m$ rectangular board consisting of square cells. Master Zhu put a leaper at position $(1, 1)$, which is the upper left cell.

The leaper is able to jump from position $(x_1, y_1)$ to position $(x_2, y_2)$ if and only if the positive integers $x_1$, $y_1$, $x_2$, and $y_2$ satisfy the following conditions:

$$\begin{array}{c} (x_2 - x_1)^2 + (y_2 - y_1)^2 = 5 \text{,} \\ x_2 > x_1 \text{,} \\ y_2 > y_1 \text{.} \\ \end{array}$$

Unfortunately, there are some obstacles on the board. The leaper can never enter a square with an obstacle.

Master Zhu wants to move the leaper to position $(n, m)$, which is the lower right cell of the board, by making zero or more jumps. Help him find the number of ways the leaper can achieve its goal. As the answer may be very large, calculate it modulo $110\,119$.

The first line of input contains one integer $T$, the number of test cases ($1 \le T \le 540$).

The first line of each test case contains three integers $n$, $m$, and $r$: the height of the board, the width of the board, and the number of obstacles on the board, respectively ($1 \leq n, m \leq 10^{18}$, $0 \leq r \leq 100$).

Then follow $r$ lines. Each of them contains two integers $x$ and $y$: coordinates of an obstacle ($1 \leq x \leq n$, $1 \leq y \leq m$). It is guaranteed that all given obstacles are distinct, and the position $(1, 1)$ contains no obstacle.

For each test case, print the answer modulo $110\,119$.