과자 줍기

Albert와 Bob은 "과자 줍기" 보드 게임을 즐겨 한다.

이 게임은 크기가 $R \times C$인 격자 보드에서 진행한다. 먼저 Bob이 $N$개의 칸을 골라 과자를 하나씩 올려 둔다. 각 칸에는 과자를 최대 1개만 올릴 수 있으며, 좌측 상단 $(1, 1)$과 우측 하단 $(R, C)$에는 과자를 올릴 수 없다. 이후 Albert는 게임 말을 $(1, 1)$ 칸에 올린 뒤 오른쪽 또는 아래로만 이동하여 $(R, C)$ 칸에 도달해야 하며, 이동한 경로를 따라 최대한 많은 과자를 줍는다.

예를 들어 아래 그림은 $R = 3$, $C = 5$, $N = 3$인 경우를 나타낸다. 편의상 과자의 위치는 크기가 $N$인 두 배열 $X$, $Y$로 행과 열을 나타내며, 이 그림의 경우 $X = [1, 1, 2]$, $Y = [3, 4, 3]$이 된다.

S로 표시된 $(1, 1)$에서 출발해 E로 표시된 $(3, 5)$ 칸으로 가는 방법은 여럿 있다. 아래 그림처럼 $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 5)$ 순으로 이동하면 과자를 1개만 줍는다.

하지만 아래 그림처럼 여섯 가지 방법으로는 과자를 총 2개 주울 수 있다.

이 그림의 경우 과자를 3개 주우면서 S칸에서 E칸으로 도달하는 방법은 없다.

Albert는 입력으로 주어진 보드에서 최대한 많은 과자를 줍는 서로 다른 방법이 몇 가지인지 궁금해졌다. Albert를 도와 이 값을 구해 보자. 위 경우의 정답은 6이다.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 $R$, $C$, $N$ 값이 공백으로 구분되어 주어진다. 다음 $N$개의 줄에는 각 줄마다 $i$번째 과자가 놓인 칸의 행 위치 $X_i$와 열 위치 $Y_i$가 공백으로 구분되어 주어진다.

각 테스트 케이스에서 시작 칸 $(1, 1)$부터 도착 칸 $(R, C)$까지 이동하며 최대한 많은 과자를 줍는 방법의 수를 한 줄에 출력한다. 이 수는 매우 클 수 있으므로 1000003으로 나눈 나머지를 출력한다.

• $1 \le T \le 20$
• $1 \le R, C \le 10^6$
• $1 \le N \le 100$
• $1 \le i \le N$인 $i$에 대하여:
  • $1 \le X_i \le R$
  • $1 \le Y_i \le C$
  • $(X_i, Y_i) \ne (1, 1)$
  • $(X_i, Y_i) \ne (R, C)$
• $1 \le i, j \le N$이고 $i \ne j$인 모든 쌍에 대하여: $(X_i, Y_i) \ne (X_j, Y_j)$