주 사부와 도약자

정사각형 칸으로 이루어진 $n \times m$ 크기의 직사각형 판을 생각하자. 주 사부는 왼쪽 위 칸인 $(1, 1)$에 도약자를 놓았다.

도약자는 양의 정수 $x\_1$, $y\_1$, $x\_2$, $y\_2$가 다음 조건을 만족할 때에만 $(x\_1, y\_1)$에서 $(x\_2, y\_2)$로 뛸 수 있다.

$\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}$

아쉽게도 판 위에는 장애물이 몇 개 있다. 도약자는 장애물이 있는 칸에 절대 들어갈 수 없다.

주 사부는 도약자를 0번 이상 뛰게 해서 판의 오른쪽 아래 칸인 $(n, m)$으로 옮기려 한다. 도약자가 목표를 이루는 방법의 수를 구하자. 답이 매우 클 수 있으므로 $110\,119$로 나눈 나머지를 계산한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 540$).

각 테스트 케이스의 첫째 줄에 세 정수 $n$, $m$, $r$이 주어진다. 이는 각각 판의 높이, 판의 너비, 판 위의 장애물 수이다 ($1 \leq n, m \leq 10^{18}$, $0 \leq r \leq 100$).

그다음 $r$개의 줄이 이어진다. 각 줄에는 장애물의 좌표 $x$와 $y$가 주어진다 ($1 \leq x \leq n$, $1 \leq y \leq m$). 주어지는 장애물은 모두 서로 다르며, $(1, 1)$에는 장애물이 없다.

각 테스트 케이스마다 답을 $110\,119$로 나눈 나머지를 출력한다.