AI Duck
Description
Rowlet recently built an AI duck! It can't do much besides walk right now, but maybe one day its full capabilities will be realized. For now, however, it is able to walk the shortest path between any two points on a grid. To make sure the duck can walk properly, Rowlet wants it to go from point $(1, 1)$ to $(N, M)$. Now, Rowlet is interested in how many possible paths the duck might take. But the owl realized the number might be too large, so the duck was given $K$ squares it must pass through. Satisfied, Rowlet took a break and went to get some more fruit (because who doesn't love fruit).
Unfortunately, two problems arose! First, Rowlet's $K$ coordinates were corrupted, meaning that it may no longer be possible to go from $(1, 1)$ to $(N, M)$ and go through the $K$ extra squares without taking steps "backwaords" (to the left or downwards). Second, Rowlet realized that the number of possible paths is still too large. Since Rowlet is still on a fruit break (who knows how long owls take to eat fruit), you are asked to find the number of suitable paths modulo* $998244353$.
*$a \mod b$ is defined as the remainder left over when dividing $a$ by $b$. For example,
$2 \mod 4 = 2$ becuase $2=0*4+2$
$5 \mod 4 = 1$ because $5=1*4+1$
$10^9 \mod 998244353 = 1755647$ because $10^9=1*998244353+1755647$, so if the answer is $10^9$, print $1755647$ instead.
The first line of input contains an integer $T (1 \leq T \leq 10^5)$, denoting the number of test cases.
Each test case contains on its first line contains three integers $N$, $M$, and $K$ $(1 \leq N, M \leq 10^5, 0 \leq K \leq 10^5)$. The following $K$ lines each contain two numbers $x_i$ $(1 \leq x_i \leq N)$ and $y_i$ $(1 \leq y_i \leq M)$, denoting the location of the $i$th incense.
It is guaranteed that the sum of $K$ over all test cases will not exceed $10^5$.
Print the number of paths modulo $998244353$.
Input
The first line of input contains an integer $T (1 \leq T \leq 10^5)$, denoting the number of test cases.
Each test case contains on its first line contains three integers $N$, $M$, and $K$ $(1 \leq N, M \leq 10^5, 0 \leq K \leq 10^5)$. The following $K$ lines each contain two numbers $x_i$ $(1 \leq x_i \leq N)$ and $y_i$ $(1 \leq y_i \leq M)$, denoting the location of the $i$th incense.
It is guaranteed that the sum of $K$ over all test cases will not exceed $10^5$.
Output
Print the number of paths modulo $998244353$.
4
3 5 0
3 5 1
2 3
3 5 2
3 4
2 2
3 5 2
2 2
1 4
15
9
6
0
Note
In the first test case, the AI duck can take any of the $15$ paths from $(1, 1)$ to $(3, 5)$.
In the second test case, the AI duck must go through $(2, 3)$.
In the last test case, the AI duck must go through $(2, 2)$ and $(1, 4)$. However, the duck cannot reach either square from the other by only moving up and right, so there are no possible paths.