You have a N x M matrix of cells. The cell (i, j) represents the cell at row i and column j. You can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1).
But K cells are blocked in the matrix(you can’t visit a blocked cell). You are given coordinates of all these cells.
You have to count number of ways to reach cell (N, M) if you begin at cell (1, 1).
Two ways are same if and only if path taken is exactly same in both ways.
First line consists of T, denoting the number of test cases. Each test case consists of N, M and K in single line. Each of the next K lines contains two space separated integers (xi, yi), denoting the blocked cell’s coordinates.
For each test case print the required answer modulo 109 + 7 in one line.
*Constraints*
Example test case 1:
No cell is blocked. 3 distinct paths are:
Example test case 2: Only one valid path:
## Input
First line consists of T, denoting the number of test cases. Each test case consists of N, M and K in single line. Each of the next K lines contains two space separated integers (xi, yi), denoting the blocked cell’s coordinates.
## Output
For each test case print the required answer modulo 109 + 7 in one line.*Constraints* 1 ≤ T ≤ 10 1 ≤ N, M ≤ 105 0 ≤ K ≤ 103 1 ≤ xi ≤ N 1 ≤ yi ≤ M
[samples]
## Note
Example test case 1:No cell is blocked. 3 distinct paths are: (1, 1) to (1, 2) to (2, 2) to (3, 2). (1, 1) to (2, 1) to (2, 2) to (3, 2). (1, 1) to (2, 1) to (3, 1) to (3, 2). Example test case 2: Only one valid path: (1, 1) to (2, 1) to (2, 2) to (2, 3).
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N, M \in \mathbb{Z}^+ $ denote the dimensions of the grid, with cells indexed from $ (1,1) $ to $ (N,M) $.
- Let $ K \in \mathbb{Z}_{\geq 0} $ denote the number of blocked cells.
- Let $ B = \{ (x_i, y_i) \mid i \in \{1, \dots, K\} \} \subseteq \{1, \dots, N\} \times \{1, \dots, M\} $ be the set of blocked cells.
**Constraints**
1. $ 1 \leq T \leq \text{unspecified} $
2. $ 1 \leq N, M \leq \text{unspecified} $
3. $ 0 \leq K \leq N \cdot M $
4. All blocked cells $ (x_i, y_i) $ satisfy $ 1 \leq x_i \leq N $, $ 1 \leq y_i \leq M $, and are distinct.
5. Start cell $ (1,1) $ and end cell $ (N,M) $ are not blocked.
**Objective**
Compute the number of paths from $ (1,1) $ to $ (N,M) $, moving only right or down, avoiding all blocked cells in $ B $, modulo $ 10^9 + 7 $.
Let $ P(i,j) $ denote the number of valid paths from $ (1,1) $ to $ (i,j) $.
Then:
$$
P(i,j) =
\begin{cases}
0 & \text{if } (i,j) \in B \\
1 & \text{if } (i,j) = (1,1) \\
P(i-1,j) + P(i,j-1) & \text{otherwise (for } i \geq 1, j \geq 1 \text{)}
\end{cases}
$$
with $ P(i,j) = 0 $ if $ i < 1 $ or $ j < 1 $.
Output $ P(N,M) \mod (10^9 + 7) $.